P2146 [NOI2015]软件包管理器 https://www.luogu.org/problemnew/show/P2146
一道树链剖分......
还算是比较裸的树剖 w
对于查询 (影响数) 的话只需要查询原本根节点值与现根节点值差异就可以了
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdio>
- #include <cmath>
- using namespace std;
- #define MAXN 100233
- //data
- int n;
- int ans[MAXN<<2],tag[MAXN<<2]={};
- struct qwq
- {
- int nex,to;
- }e[MAXN<<1];
- int h[MAXN],son[MAXN],siz[MAXN],fa[MAXN],top[MAXN],id[MAXN],dep[MAXN];
- int tot=0,cnt=0;
- //data_end.
- void add(int x,int y)
- {
- e[++tot].to=y;
- e[tot].nex=h[x];
- h[x]=tot;
- }
- //dfs<<1
- inline void dfs_fir(int x,int f,int dept)
- {
- dep[x]=dept;
- fa[x]=f;
- siz[x]=1;
- int maxn=-1;
- for (int i=h[x],y;i;i=e[i].nex)
- {
- y=e[i].to;
- if (y==f) continue;
- dfs_fir(y,x,dept+1);
- siz[x]+=siz[y];
- if (siz[y]>maxn)
- {
- son[x]=y;
- maxn=siz[y];
- }
- }
- }
- inline void dfs_sec(int x,int ft)
- {
- id[x]=++cnt;
- top[x]=ft;
- if (!son[x]) return;
- dfs_sec(son[x],ft);
- int y;
- for (int i=h[x];i;i=e[i].nex)
- {
- y=e[i].to;
- if (y==fa[x]||y==son[x]) continue;
- dfs_sec(y,y);
- }
- }
- //dfs_end.
- //segment_tree
- #define ll long long
- #define leftson cur<<1
- #define rightson cur<<1|1
- #define mid ((l+r)>>1)
- #define push_up ans[cur]=ans[leftson]+ans[rightson]
- #define push_down lazyadd(leftson,l,mid,tag[cur]); lazyadd(rightson,mid+1,r,tag[cur]); tag[cur]=-1
- void lazyadd(int cur,int l,int r,int del)
- {
- if (del==-1) return;
- ans[cur]=(r-l+1)*del;
- tag[cur]=del;
- }
- inline void change(int adl,int adr,int cur,int l,int r,int del)
- {
- if (adl<=l&&r<=adr)
- {
- ans[cur]=(r-l+1)*del;
- tag[cur]=del;
- return;
- }
- push_down;
- if (adl<=mid) change(adl,adr,leftson,l,mid,del);
- if (adr>mid) change(adl,adr,rightson,mid+1,r,del);
- push_up;
- }
- #undef ll
- //segment_tree_end.
- void upd(int x,int y,int del)
- {
- while (top[x]!=top[y])
- {
- if (dep[top[x]]<dep[top[y]]) swap(x,y);
- change(id[top[x]],id[x],1,1,n,del);
- x=fa[top[x]];
- }
- if (dep[x]>dep[y]) swap(x,y);
- change(id[x],id[y],1,1,n,del);
- }
- int main()
- {
- scanf("%d",&n);
- int a;
- for (int i=2;i<=n;i++)
- {
- scanf("%d",&a);
- add(a+1,i);
- }
- for (int i=1;i<=(n<<2);i++)
- {
- tag[i]=-1;
- }
- dfs_fir(1,1,1);
- dfs_sec(1,1);
- int q;
- scanf("%d",&q);
- string s;
- int TAT;
- for (int i=1;i<=q;i++)
- {
- cin>>s;
- scanf("%d",&a);
- a++;
- TAT=ans[1];
- if (s[0]=='u')
- {
- change(id[a],id[a]+siz[a]-1,1,1,n,0);
- printf("%d\n",abs(TAT-ans[1]));
- continue;
- }
- upd(1,a,1);
- printf("%d\n",abs(TAT-ans[1]));
- }
- }
残废了...
P2146 [NOI2015]软件包管理器
来源: http://www.bubuko.com/infodetail-3074457.html