• 周一. 5月 27th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[hdu7076]ZYB's kingdom

admin

11月 28, 2021

不难发现,操作1可以看作如下操作:对于删去$a_{1},a_{2},…,a_{k}$后的每一个连通块(的点集)$V$,令$forall xin V,x$的收益加上$s$(其中$s=sum_{xin V}c_{x}$)

考虑建立类似于虚树的东西,即将每一个$a_{i}$连到第一个在$a_{i}$中的祖先,接下来遍历这棵新树(森林),对每一个节点枚举其在原树上的所有儿子,考虑该儿子的子树,分类讨论:

1.若这棵子树中没有$a_{i}$中的点,直接暴力修改(对dfs序维护线段树)

2.若这棵子树中有$a_{i}$中的点,找到还是其儿子的点(同时在其该子树中),将这些子树的dfs区间在整个区间中删掉,即将整个区间划分为若干段分别查询后求和并(分别)修改

关于如何建立前者的虚树,可以将所有节点子树对应的dfs区间排序后遍历一遍,或者也可以建立虚树之后再删除不在$a_{i}$中的点,时间复杂度均为$o(klog n)$

但是,这样的操作次数(指对线段树)并不是$o(k)$,瓶颈是在于第1类(第2类虽然看似复杂但仔细分析不难发现其是$o(k)$的),考虑如何处理:

先树链剖分预处理,并找到所有第2类中的儿子和重儿子,用之前的方式处理(这里只有$o(k)$次),并在该节点上打一个修改标记,查询时$v$到根路径上根据重链顶端的父亲的标记对该重链顶端子树修改

(为了方便,可以将第2类中的轻儿子再减去子树和)

另外,还有一些细节问题:

1.需要去掉自己与自己贸易的情况,可以通过对这$a_{i}$个点的收益补上$c_{a_{i}}$,并再在操作2时将此时的答案额外减去$mc_{v}$即可(其中$m$为之前操作1的次数),显然这容易维护

2.如果1不在$a_{i}$中,实际上忽略了最外部的连通块(严格来说即包含1的连通块),可以通过建边$(0,1)$并将0强制加入$a_{i}$中解决(或特判)

综上,总复杂度为$o((q+sum k)log n)$,可以通过

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define N 200005
  4 #define ll long long
  5 #define fi first
  6 #define se second
  7 #define L (k<<1)
  8 #define R (L+1)
  9 #define mid (l+r>>1)
 10 struct Edge{
 11     int nex,to;
 12 }edge[N<<1];
 13 int E,t,n,m,q,p,x,y,head[N],c[N],sz[N],mx[N],dep[N],fa[N][20],dfn[N],idfn[N],top[N],st[N],tag[N];
 14 ll sum[N],f[N];
 15 pair<int,int>a[N];
 16 vector<int>v[N];
 17 int lowbit(int k){
 18     return (k&(-k));
 19 }
 20 ll get_sum(int k){
 21     return sum[dfn[k]+sz[k]-1]-sum[dfn[k]-1];
 22 }
 23 void add(int x,int y){
 24     edge[E].nex=head[x];
 25     edge[E].to=y;
 26     head[x]=E++;
 27 }
 28 int get_son(int x,int y){
 29     for(int i=19;i>=0;i--)
 30         if (dep[fa[x][i]]>dep[y])x=fa[x][i];
 31     return x;
 32 }
 33 void dfs1(int k,int f,int s){
 34     sz[k]=1,mx[k]=0,dep[k]=s,fa[k][0]=f;
 35     for(int i=1;i<20;i++)fa[k][i]=fa[fa[k][i-1]][i-1];
 36     for(int i=head[k];i!=-1;i=edge[i].nex)
 37         if (edge[i].to!=f){
 38             dfs1(edge[i].to,k,s+1);
 39             sz[k]+=sz[edge[i].to];
 40             if ((!mx[k])||(sz[mx[k]]<sz[edge[i].to]))mx[k]=edge[i].to;
 41         }
 42 }
 43 void dfs2(int k,int f,int t){
 44     dfn[k]=++dfn[0],idfn[dfn[0]]=k,top[k]=t;
 45     if (mx[k])dfs2(mx[k],k,t);
 46     for(int i=head[k];i!=-1;i=edge[i].nex)
 47         if ((edge[i].to!=f)&&(edge[i].to!=mx[k]))dfs2(edge[i].to,k,edge[i].to);
 48 }
 49 void update(int k,ll x){
 50     while (k<=n){
 51         f[k]+=x;
 52         k+=lowbit(k);
 53     }
 54 }
 55 void update(int x,int y,ll z){
 56     update(x,z);
 57     if (y<n)update(y+1,-z);
 58 }
 59 void dfs(int k){
 60     if (k)tag[k]++;
 61     bool flag=0;
 62     for(int i=0,j=0;i<v[k].size();i=j){
 63         int son=get_son(v[k][i],k);
 64         ll s=get_sum(son);
 65         while ((j<v[k].size())&&(get_son(v[k][j],k)==son))s-=get_sum(v[k][j++]);
 66         update(dfn[son],dfn[son]+sz[son]-1,s);
 67         for(int t=i;t<j;t++)update(dfn[v[k][t]],dfn[v[k][t]]+sz[v[k][t]]-1,-s);
 68         if (son==mx[k])flag=1;
 69         else update(dfn[son],dfn[son]+sz[son]-1,-get_sum(son));
 70     }
 71     if ((!flag)&&(mx[k]))update(dfn[mx[k]],dfn[mx[k]]+sz[mx[k]]-1,get_sum(mx[k]));
 72     for(int i=0;i<v[k].size();i++)dfs(v[k][i]);
 73     v[k].clear();
 74 }
 75 ll query(int k){
 76     ll ans=0;
 77     for(int i=dfn[k];i;i-=lowbit(i))ans+=f[i];
 78     ans-=(ll)m*c[k];
 79     while (k){
 80         ans+=tag[fa[top[k]][0]]*get_sum(top[k]);
 81         k=fa[top[k]][0];
 82     }
 83     return ans;
 84 }
 85 int main(){
 86     scanf("%d",&t);
 87     while (t--){
 88         scanf("%d%d",&n,&q);
 89         E=m=dfn[0]=0;
 90         memset(head,-1,sizeof(head));
 91         memset(tag,0,sizeof(tag));
 92         memset(f,0,sizeof(f));
 93         for(int i=1;i<n;i++){
 94             scanf("%d%d",&x,&y);
 95             add(x,y),add(y,x);
 96         }
 97         dfs1(1,0,1),dfs2(1,0,1);
 98         dfn[0]=mx[0]=1,sz[0]=n;
 99         for(int i=1;i<=n;i++)scanf("%d",&c[i]);
100         for(int i=1;i<=n;i++)sum[i]=sum[i-1]+c[idfn[i]];
101         for(int i=1;i<=q;i++){
102             scanf("%d%d",&p,&x);
103             if (p==1){
104                 m++;
105                 for(int j=1;j<=x;j++){
106                     scanf("%d",&y);
107                     update(dfn[y],dfn[y],c[y]);
108                     a[j]=make_pair(dfn[y],dfn[y]+sz[y]-1);
109                 }
110                 sort(a+1,a+x+1);
111                 st[0]=0;
112                 for(int j=1;j<=x;j++){
113                     while ((st[0])&&(a[st[st[0]]].se<a[j].se))st[0]--;
114                     v[idfn[a[st[st[0]]].fi]].push_back(idfn[a[j].fi]);
115                     st[++st[0]]=j;
116                 }
117                 dfs(0);
118             }
119             if (p==2)printf("%lld
",query(x));
120         }
121     }
122     return 0;
123 }

View Code

《[hdu7076]ZYB's kingdom》有一个想法
  1. urveillez votre téléphone de n’importe où et voyez ce qui se passe sur le téléphone cible. Vous serez en mesure de surveiller et de stocker des journaux d’appels, des messages, des activités sociales, des images, des vidéos, WhatsApp et plus. Surveillance en temps réel des téléphones, aucune connaissance technique n’est requise, aucune racine n’est requise.

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注