题目及数据:
https://www.lanzous.com/i1xdr8h
预计分数:$100+ 100 +60 = 260$
实际得分:$100 + 100 + 0 = 200$
我这次检查了三遍绝对没算错!!!
上来看T1,咦?我好像做过这题在仙人掌上的版本。。树上更简单吧。。写+拍 1h,期间拍出了暴力的两个bug。。。
看T2,好难啊,不会做啊 qwq。。然后开始强行套算法。恩。把单调队列套进去发现是可行的。。而且好像还可以无视题目的一些性质。。嘿嘿嘿这题有加强版了
T3更神仙。。想了一个并查集优化暴力的$n^2$算法,然后写挂了。。。自己造的输出跑的贼快,一上评测机就死循环。。
因为昨天晚上打cf特别困,而且自我感觉$260$应该不低了,就睡了一个半小时。。。。。。。。。
听大佬们说是原题啊Orz
我居然不知道 我好像是做过然后忘的一干二净。。
很显然,把路径拆开,判断lca之间的关系即可
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cstring>
#define getchar() ((p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
using namespace std;
const int MAXN = 1e5 + 10;
char buf[(1 << 21)], *p1 = buf, *p2 = buf;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int T, N, Q, fa[MAXN], dep[MAXN], top[MAXN], son[MAXN], siz[MAXN];
vector<int> v[MAXN];
void init() {
for(int i = 1; i <= N; i++) v[i].clear();
memset(top, 0, sizeof(top));
memset(son, 0, sizeof(son));
}
void dfs1(int x, int _fa) {
siz[x] = 1; fa[x] = _fa;
for(int i = 0; i < v[x].size(); i++) {
int to = v[x][i];
if(to == _fa) continue;
dep[to] = dep[x] + 1;
dfs1(to, x);
siz[x] += siz[to];
if(siz[to] > siz[son[x]]) son[x] = to;
}
}
void dfs2(int x, int topf) {
top[x] = topf;
if(!son[x]) return ;
dfs2(son[x], topf);
for(int i = 0; i < v[x].size(); i++) {
int to = v[x][i];
if(top[to]) continue;
dfs2(to, to);
}
}
int LCA(int x, int y) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
return x;
}
bool check(int a, int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
if(LCA(a, x) == a && LCA(a, y) == y) return 1;
else return 0;
}
int main() {
freopen("railway.in", "r", stdin);
freopen("railway.out", "w", stdout);
T = read();
while(T--) {
N = read(); Q = read();
init();
for(int i = 1; i <= N - 1; i++) {
int x = read(), y = read();
v[x].push_back(y); v[y].push_back(x);
}
dep[1] = 1; dfs1(1, 0);
dfs2(1, 1);
while(Q--) {
int xx1 = read(), yy1 = read(), xx2 = read(), yy2 = read();
int lca1 = LCA(xx1, yy1), lca2 = LCA(xx2, yy2);
if(check(lca1, xx2, lca2) || check(lca1, yy2, lca2) || check(lca2, xx1, lca1) || check(lca2, yy1, lca1)) puts("YES");
else puts("NO");
}
}
return 0;
}
式子化简完了之后应该是求
$$\sum_{i = 1}^n sum_{j = 1}^i mx - mn$$
其中
$mx = max(a[j], a[j+1], \dots a[i])$
$mn = min(a[j], a[j+1], \dots a[i])$
单调栈维护即可。。。。
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#define LL long long
using namespace std;
const LL MAXN = 1e5 + 10;
inline LL read() {
char c = getchar(); LL x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
LL T, N;
LL a[MAXN], q[MAXN];
LL solve() {
LL h = 1, t = 0, ans = 0, sum = 0;
for(LL i = 1; i <= N; i++) {
while(h <= t && a[i] > a[q[t]]) sum -= a[q[t]] * (q[t] - q[t - 1]), t--;
q[++t] = i;
ans += a[i] * (q[t] - q[t - 1]) + sum;
sum += a[i] * (q[t] - q[t - 1]);
}
return ans;
}
int main() {
freopen("count.in", "r", stdin);
freopen("count.out", "w", stdout);
T = read();
while(T--) {
N = read();
for(LL i = 1; i <= N; i++) a[i] = read();
LL ans = solve();
for(LL i = 1; i <= N; i++) a[i] = -a[i];
LL ans2 = solve();
cout << ans + ans2 << endl;
}
return 0;
}
不明白出这种题有什么意义。。。
dsu on tree, set,这都是noip知识点????
而且标算好像就是在想尽各种方法优化暴力。。。
考虑直接算一条边的贡献
首先考虑暴力怎么算
对于一条边来说,如果子树内有连续的区间,比如$[1, 2, 3, 4]$那么在统计他们的答案时显然不会经过该边,他们对答案的贡献为$\frac{n(n -1)}{2} $
用总贡献减去即可。
然后可以分成子树内和子树外讨论,子树内用并查集维护,子树外用set维护并查集的补集
做完了。。。
代码里面的solve函数是抄的标算,,,实在写不出来啊qwq
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN = 1e5 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, dep[MAXN], siz[MAXN], son[MAXN], dsu[MAXN], Son, vis[MAXN], ds[MAXN];
vector<int> v[MAXN];
set<int> s;
LL AnsOut, AnsIn, ans;
void dfs(int x, int _fa) {
siz[x] = 1;
for(int i = 0; i < v[x].size(); i++) {
int to = v[x][i]; if(to == _fa) continue;
dfs(to, x);
siz[x] += siz[to];
if(siz[to] > siz[son[x]]) son[x] = to;
}
}
LL calc(LL x) {
return x * (x - 1) / 2;
}
void Clear() {
s.clear(); AnsOut = calc(N); AnsIn = 0;
s.insert(0); s.insert(N + 1);
}
int find(int x) {
return dsu[x] == x ? dsu[x] : dsu[x] = find(dsu[x]);
}
void solve(int x) {
s.insert(x);
set<int>::iterator s1, s2, it;
s1 = s2 = it = s.find(x);
s1--; s2++;
AnsOut -= calc((*s2) - (*s1) - 1);
AnsOut += calc((*s2) - (*it) - 1) + calc((*it) - (*s1) - 1);
vis[x] = 1;
if(vis[x - 1]) {
int fx = find(x - 1), fy = find(x);
AnsIn += ds[fx] * ds[fy];
dsu[fx] = fy;
ds[fy] += ds[fx];
}
if(vis[x + 1]) {
int fx = find(x + 1), fy = find(x);
AnsIn += ds[fx] * ds[fy];
dsu[fx] = fy;
ds[fy] += ds[fx];
}
}
void Add(int x, int fa) {
solve(x);
for(int i = 0; i < v[x].size(); i++) {
int to = v[x][i];
if(to == fa || to == Son) continue;
Add(to, x);
}
}
void Delet(int x, int fa) {
vis[x] = 0; ds[x] = 1; dsu[x] = x;
for(int i = 0; i < v[x].size(); i++) {
int to = v[x][i];
if(to == fa) continue;
Delet(to, x);
}
}
void dfs2(int x, int fa, int opt) {
for(int i = 0; i < v[x].size(); i++) {
int to = v[x][i];
if(to == fa || (to == son[x])) continue;
dfs2(to, x, 0);
}
if(son[x]) dfs2(son[x], x, 1); Son = son[x];
Add(x, fa);
ans += calc(N) - AnsIn - AnsOut;
if(opt == 0) Delet(x, fa), Clear(), Son = 0;
}
main() {
N = read();
for(int i = 1; i <= N - 1; i++) {
int x = read(), y = read();
v[x].push_back(y); v[y].push_back(x);
}
for(int i = 1; i <= N; i++) dsu[i] = i, ds[i] = 1;
dep[1] = 1; dfs(1, 0);
Clear();
dfs2(1, 0, 0);
cout << ans;
return 0;
}
/*
10
1 9
9 7
9 5
5 3
9 4
4 8
1 10
1 2
3 6
4
1 4
1 3
2 4
*/