失踪人口回归
VP 打的
A. Sasha and Array Coloring
int n;
int a[maxN];
void solve(){
n=rd();
fp(i,1,n) a[i]=rd();
sort(a+1,a+n+1);
ll ans=0;
for(int i=1;i*2<=n;++i)
ans+=(a[n-i+1]-a[i]);
cout << ans << endl;
}
B. Long Long
int n;
int a[maxN];
void solve(){
n=rd();
ll sum=0,last=1,step=0;
fp(i,1,n){
a[i]=rd();
if(last==1&&a[i]<0) last=0,step++;
else if(last==0&&a[i]>0) last=1;
sum+=abs(a[i]);
}
cout << sum << " " << step << endl;
}
C. Sum in Binary Tree
ll n;
void solve(){
ll n =lrd();
ll sum=0;
sum++;
while(n!=1){
sum+=n;
n>>=1;
}
cout << sum << endl;
}
D. Apple Tree
const int maxN=2*1e5+10;
int n,q,idx;
int siz[maxN],dep[maxN],dfn[maxN];
ll leaf[maxN];
vector<int> g[maxN];
inline void dfs(int now,int f){
dep[now]=dep[f]+1;
dfn[now]=++idx;
siz[now]=1;
for(int x:g[now])
if(x!=f) dfs(x,now),siz[now]+=siz[x],leaf[now]+=leaf[x];
if(g[now].size()==1&&g[now][0]==f) leaf[now]=1;
}
void solve(){
n=rd();
fp(i,1,n-1){
int u=rd(),v=rd();
g[u].eb(v),g[v].eb(u);
}
dfs(1,1);
q=rd();
while(q--){
ll ans=0;
int a=rd(),b=rd();
if(dep[a]>dep[b]) swap(a,b);
if(dfn[a]<=dfn[b]&&dfn[b]<=dfn[a]+siz[a]-1){
ans+=(ll)(leaf[a]-leaf[b])*leaf[b];
ans+=(ll)leaf[b]*leaf[b];
}
else ans+=(ll)(leaf[a]*leaf[b]);
cout << ans << endl;
}
met(siz,0);
met(dep,0),met(dfn,0),met(leaf,0);
idx=0;
fp(i,1,n) g[i].clear();
}
E. Tracking Segments
一眼二分，没了
const int maxN=1e5+10;
int n,m,q;
int a[maxN],ch[maxN],pre[maxN];
pii line[maxN];
void solve(){
n=rd(),m=rd();
fp(i,1,m) line[i].first=rd(),line[i].second=rd();
q=rd();
fp(i,1,q) ch[i]=rd();
int l=1,r=q,ans=-1;
while(l<=r){
int mid=(l+r)>>1;
fp(i,1,mid) a[ch[i]]=1;
fp(i,1,n) pre[i]=pre[i-1]+a[i];
int flag=0;
fp(i,1,m){
int s=line[i].first,e=line[i].second;
if((pre[e]-pre[s-1])*2>(e-s+1)){
flag=1;break;
}
}
met(a,0);
met(pre,0);
if(flag){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
cout << ans <<endl;
}
F. Omsk Metro
动态给出一棵 \(n\)个节点的树，每个节点有一个权值，权值为 \(1\) 或 \(-1\)，给出若干次询问，询问 \(u\)，\(v\) 之间的路径上是否有一个子串的和为 \(k\)
\(n\in [1,10^5]\)
这里加一减一，则增长是连续的，所以我们要找到最大的和最小的子段和，然后判断是不是在这个区间里就可以了
这里使用了倍增实现
inline int logx(int n) {
int result = 0;
if(n&0xffff0000) {result += 16; n >>= 16; }
if(n&0x0000ff00) {result += 8; n >>= 8; }
if(n&0x000000f0) {result += 4; n >>= 4; }
if(n&0x0000000c) {result += 2; n >>= 2; }
if(n&0x00000002) {result += 1; n >>= 1; }
return result;
}
const int maxN = 2 * 1e5 + 10;
int n;
int acc[maxN][20], dep[maxN], va[maxN], fa[maxN];
struct node {
int minx, maxx;
int mal, mar;
int mil, mir, sum;
} f[maxN][20], g[maxN];
node update(node x, node y) {
node z;
z.mal = max(x.mal, y.mal + x.sum);
z.mar = max(y.mar, x.mar + y.sum);
z.mil = min(x.mil, y.mil + x.sum);
z.mir = min(y.mir, x.mir + y.sum);
z.minx = min(x.minx, min(y.minx, x.mir + y.mil));
z.maxx = max(x.maxx, max(y.maxx, x.mar + y.mal));
z.sum = x.sum + y.sum;
return z;
}
void add(int x) {
for (int i = 0, v = acc[x][i]; v; v = acc[x][++i]) acc[x][i + 1] = acc[v][i];
dep[x] = dep[acc[x][0]] + 1;
g[x].minx = min(va[x], 0), g[x].maxx = max(va[x], 0);
g[x].mal = g[x].mar = max(0, va[x]);
g[x].mil = g[x].mir = min(0, va[x]);
g[x].sum = va[x];
f[x][0] = g[x];z
for (int i = 0, v = acc[x][i]; dep[x] >= (1 << (i + 1)); ++i,v = acc[x][i]){
f[x][i + 1] = update(f[x][i], f[v][i]);
}
}
inline int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int gap = dep[x] - dep[y], bit = logx(gap); gap; gap -= (1<<bit), bit = logx(gap)) x = acc[x][bit];
for (int i = logx(dep[x]); ~i; --i) if (acc[x][i] != acc[y][i]) x = acc[x][i], y = acc[y][i];
return (x == y) ? x : acc[x][0];
}
node get_chain(int u, int c) {
node ans;
ans.sum=-inf;
int flag = 0;
for(int x=dep[u]-dep[c],bit=logx(x);x>0;x-=(1<<(bit)),bit=logx(x)) {
if(!flag)
ans=f[u][bit],flag=1;
else
ans=update(ans,f[u][bit]);
u=acc[u][bit];
}
return ans;
}
void M_clear(){
node p=node{0,0,0,0,0,0,0};
fp(i,1,n){
va[i]=0,dep[i]=0,fa[i]=0;
met(acc[i],0);
fp(j,0,20) f[i][j]=p;
g[i]=p;
}
}
void solve() {
int op = rd();
dep[1] = 1;
n = 1;
va[1]=1;
g[n].minx = min(va[n], 0), g[n].maxx = max(va[n], 0);
g[n].mal = g[n].mar = max(0, va[n]);
g[n].mil = g[n].mir = min(0, va[n]);
g[n].sum = va[n];
f[n][0] = g[n];
while (op--) {
char ch = getchar();
if (ch == '+') {
fa[++n] = rd();
acc[n][0] = fa[n];
va[n] = rd();
add(n);
} else {
int u = rd(), v = rd(), k = rd();
int c = lca(u, v);
if (dep[u] < dep[v]) swap(u, v);
node ans;
if(c==u||c==v){
ans=get_chain(u,c);
if(ans.sum==-inf) ans=g[c];
else ans=update(ans,g[c]);
}
else {
ans=get_chain(u,c);
ans=update(ans,g[c]);
node p=get_chain(v,c);
swap(p.mil,p.mir);
swap(p.mar,p.mal);
ans=update(ans,p);
}
if(ans.minx<=k&&ans.maxx>=k)
cout << "YES" << endl;
else cout << "NO" << endl;
}
}
M_clear();
}