「Ynoi2019」美好的每一天~ 不连续的存在

「Ynoi2019」美好的每一天~ 不连续的存在

六月 26, 2020 · OI 题解

给数组 $A$ 和 $n$ 个节点的树，每个点有一个 $1$ 到 $x$ 颜色。

$m$ 次查询，每次查询树上只保留 $[l,r]$ 内的所有节点，设一个极大连通块中出现奇数次数的颜色个数为 $t$，则其对答案的贡献为 $A_t$ ，即答案是所有连通块贡献的和，询问相互独立。

$1\leq n,m\leq 10^5$，$1\leq x,A_i \leq 10^4$。

题解

退役选手被lxl抓过来写题解

考虑用单增莫队维护，想了想容易发现复杂度不对。

莫队的端点移动需要启发式合并维护信息，而启发式合并的复杂度基于我们可以把势能均摊，如果我们在分块时基于势能呢？

单增莫队的复杂度主要产生于以下两个部分（假设把询问分为 $S$ 块）：

  • 左端点左移：对于每个端点都会贡献 $O(S)$，故这一部分的总势能是 $O(S n \sqrt n)$ 的
  • 右端点右移：每个块内的询问会对每个块内的端点贡献 $O(1)$ 次，可以通过构造询问分布，卡满这部分的势能和。
  • 回滚后缀的右端点右移操作：回滚操作于增加操作复杂度相同。

有没有救呢？当然是有的。注意左端点的移动势能是只和块数相关的。瓶颈在于右端点的移动：对于一个区间 $[l,r]$，端点 $i$ 在右端点移动时贡献的势能为 $A_i$，则一次经过该区间的询问产生的势能至多为 $\sum_{i=l+1}^r A_i$。

理清思路后题解就很显然了，我们先处理出每个端点的势能 $B_i$（在 $1 \ldots (i-1)$ 后插入 $i$ 贡献的势能，上文提到的势能 $A_i$ 是一定有 $A_i \leq B_i$ 的）。然后从右到左对势能分块。

如果加入当前端点后当前栈内端点的势能和大于 $\sqrt {n} \log n$ 就将栈内元素分为一块。由于所有被分配到这个块的询问都是经过块的不会贡献势能的左端点，而其余端点贡献的势能和是一定小于 $\sqrt n \log n$ 的。

总时间复杂度 $O((n+Q)\sqrt n \log n)$。

卡常技巧

本题卡常的一比，毒瘤 lxl（（

  1. 手动调整块大小
  2. 作栈/队列功能的 std::vector<T> 换成手写（不知道为什么我做到这这步就过了）
  3. 手写 bitset（我鸽了）
  4. 手写可合并的 vector（然而我手写了一个还打不过 std::vector<T>，我已经报警了）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
#include<bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC target("popcnt")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("inline-functions-called-once")
#define log(...) (void(0))
// #define log(...) fprintf(stderr,__VA_ARGS__)
#define debug log("\33[2mPassing [%s] in LINE %d\33[0m\n",__FUNCTION__,__LINE__);
const int S=1<<21; char ibuf[S],*iS,*iT,obuf[S],*oS=obuf,*oT=oS+S-1;
#define flush() (fwrite(obuf,1,oS-obuf,stdout),oS=obuf,void())
#define getchar() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,S,stdin),(iS==iT?EOF:*iS++)):*iS++)
#define putchar(x) (*oS++=(x),oS==oT?flush():void())
struct Flusher_{~Flusher_(){flush();}}flusher_;
template<class T> inline void read(T &x){
  x=0; register char c=getchar(); register bool f=0;
  while(!isdigit(c))f^=c=='-',c=getchar();
  while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
}
template<class T> inline void print(T x){
  if(x<0)putchar('-'),x=-x;
  if(x>9)print(x/10); putchar(x%10+'0');
}
template<class T> inline void print(T x,char c){print(x),putchar(c);}
const int N=1e5+10,M=1e4+10,S1=256,S2=4;
unsigned int clockSum;
int n,m,x,blocks,a[N],c[N],bln[N],anc[N],pre[N],siz[N],ans[N];
std::vector<int> G[N];
template<class T,int N> struct static_vector{
  T a[N];
  size_t top;
  inline T& operator[](size_t k){return a[k];}
  inline T operator[](size_t k)const{return a[k];}
  inline T& back(){return a[top-1];}
  inline T back()const{return a[top-1];}
  inline void clear(){top=0;}
  inline void pop_back(){top--;}
  inline void push_back(const T &e){a[top++]=e;}
  inline size_t size(){return top;}
};
struct query{
  int l,r,id;
};
std::vector<query> q;
namespace tree{
  int ans,delta,anc[N];
  bool roll,mrk[N];
  std::bitset<M> mem[N/S2+5];
  static_vector<size_t,(N/S2+5)> rub;
  static_vector<std::tuple<int,int,int>,(N<<1)> history;
  struct unicom_block{
    int id,cnt,bitset,key[S2];
    std::vector<int> vec;
    inline unicom_block(){bitset=-1,memset(key,-1,sizeof(key));}
    inline void clear(){
      if(~bitset)mem[bitset].reset(),rub.push_back(bitset),bitset=-1;
      cnt=0,vec.clear(),memset(key,-1,sizeof(key));
    }
    inline void pushup(int k){
      ans-=a[cnt];
      if(~bitset){
        if(mem[bitset][k]){
          mem[bitset][k]=0,--cnt;
        }else{
          mem[bitset][k]=1,++cnt;
        }
      }else{
        for(int i=0;i<S2;i++)if(key[i]==k){key[i]=-1,--cnt; goto out;}
        for(int i=0;i<S2;i++)if(key[i]==-1){key[i]=k,++cnt; goto out;}
        bitset=rub.back(),rub.pop_back();
        mem[bitset][k]=1,++cnt;
        for(int i=0;i<S2;i++)mem[bitset][key[i]]=1;
      }
      out:ans+=a[cnt];
    }
  }uni[N];
  inline void merge(unicom_block &u,unicom_block &v){
    for(int i:u.vec)v.pushup(i);
  }
  int find(int x){return x==anc[x]?x:find(anc[x]);}
  void reset(){
    log("\e[2mreset\e[0m\n");
    ans=roll=0;
    for(int i=1;i<=n;i++){
      anc[i]=i;
      if(mrk[i])uni[i].clear(),mrk[i]=0;
    }
  }
  void add(int x){
    log("\e[2madd %d\e[0m\n",x);
    ans+=a[0]; if(roll)delta+=a[0];
    if(roll)history.push_back({0,x,0});
    mrk[x]=1;
    uni[x].vec.push_back(c[x]),uni[x].pushup(c[x]);
    for(int i=0;i<G[x].size();i++)if(mrk[G[x][i]]){
      int y=G[x][i],u=find(x),v=find(y);
      if(uni[u].vec.size()>uni[v].vec.size())std::swap(u,v);
      // log("merge %d[%d %lu] %d[%d %lu]\n",x,u,uni[u].vec.size(),y,v,uni[v].vec.size());
      if(roll)history.push_back({u,v,anc[u]});
      merge(uni[u],uni[v]);
      uni[v].vec.insert(uni[v].vec.end(),uni[u].vec.begin(),uni[u].vec.end()),anc[u]=v;
      ans-=a[uni[u].cnt]; if(roll)delta-=a[uni[u].cnt];
    }
  }
  int query(){return ans;}
  void rollback(){
    log("\e[2mrollback\e[0m\n");
    ans-=delta,delta=0;
    for(int u,v,t,i=(int)history.size()-1;i>=0;i--){
      std::tie(u,v,t)=history[i];
      if(u){
        anc[u]=t;
        for(int i:uni[u].vec)uni[v].vec.pop_back();
        merge(uni[u],uni[v]);
      }else{
        mrk[v]=0,uni[v].pushup(c[v]),uni[v].clear();
      }
    }
    history.clear();
  }
}
struct block{
  int id,l,r;
  std::vector<query> q;
  void init(){
    for(int i=l;i<=r;i++)bln[i]=id;
  }
  void solve(){
    std::sort(q.begin(),q.end(),[](const query &a,const query &b){return a.l>b.l;});
    tree::reset();
    int cur=l,i;
    for(const auto &it:q){
      // log("\e[34mquery {%d %d}\e[0m block[%d]={%d %d}\n",it.l,it.r,id,l,r);
      while(it.l<=cur)tree::add(cur--);
      for(tree::roll^=1,i=l+1;i<=it.r;i++)tree::add(i);
      ans[it.id]=tree::query();
      tree::roll^=1,tree::rollback();
    }
  }
}block[S1<<1];
void build(){
  std::function<int(int)> find=[&](int x){return anc[x]==x?x:anc[x]=find(anc[x]);};
  for(int i=1;i<=n;i++)anc[i]=i,siz[i]=1;
  for(int u=1;u<=n;u++){
    for(int v:G[u])if(v<u){
      int fu=find(u),fv=find(v); if(fu==fv)continue;
      if(siz[fu]>siz[fv])std::swap(fu,fv);
      pre[u]+=siz[fu],anc[fu]=fv,siz[fv]+=siz[fu];
    }
    pre[u]+=G[u].size();
  }
  int S=std::accumulate(pre+1,pre+n+1,0)/S1+1;
  fprintf(stderr,"> block limit = %d\n",S);
  std::vector<std::tuple<int,int,int>> seq={{n+1,n,0}};
  for(int i=n;i>=1;i--){
    std::get<0>(seq.back())--,std::get<2>(seq.back())+=pre[i];
    if(i==1||std::get<2>(seq.back())+pre[i]>S)seq.push_back({i,i-1,0});
  }
  seq.pop_back(),std::reverse(seq.begin(),seq.end()),blocks=seq.size();
  for(int _,i=0;i<blocks;i++){
    std::tie(block[i].l,block[i].r,_)=seq[i];
    // log("%d [%d %d] %d\n",i,block[i].l,block[i].r,std::accumulate(pre+block[i].l,pre+block[i].r+1,0));
    block[i].id=i,block[i].init();
  }
}
void solve(){
  for(int i=1;i<=n;i++)tree::uni[i].id=i;
  for(const auto &it:q)if(bln[it.l]==bln[it.r]){
    // log("\e[34mquery {%d %d}\e[0m all belong to %d\n",it.l,it.r,bln[it.l]);
    tree::reset();
    for(int i=it.l;i<=it.r;i++)tree::add(i);
    ans[it.id]=tree::query();
  }else{
    block[bln[it.r]].q.push_back(it);
  }
  for(int i=0;i<blocks;i++)block[i].solve();
}
int main(){
  for(int i=0;i<N/S2+5;i++)tree::rub.push_back(i);
#ifdef memset0
  freopen("2.in","r",stdin);
  freopen("2.out","w",stdout);
#endif
  read(n),read(m),read(x);
  for(int i=1;i<=n;i++)read(c[i]),--c[i];
  for(int u,v,i=1;i<n;i++){
    read(u),read(v);
    G[u].push_back(v),G[v].push_back(u);
  }
  for(int i=0;i<=x;i++)read(a[i]);
  build();
  // log("\e[31mpre\e[0m = "); for(int i=1;i<=n;i++)log("%d%c",pre[i]," \n"[i==n]);
  // log("\e[31mbln\e[0m = "); for(int i=1;i<=n;i++)log("%d%c",bln[i]," \n"[i==n]);
  for(int l,r,i=1;i<=m;i++){
    read(l),read(r);
    q.push_back({l,r,i});
  }
  solve();
  for(int i=1;i<=m;i++)print(ans[i],'\n');
  fprintf(stderr,"clocks: %.4lf\n",clockSum/(double)CLOCKS_PER_SEC);
  fprintf(stderr,"clocks: %.4lf\n",clock()/(double)CLOCKS_PER_SEC);
}

手写 vector 且没通过的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
#include<bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC target("popcnt,tune=native")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("inline-functions-called-once")
#define log(...) (void(0))
// #define log(...) fprintf(stderr,__VA_ARGS__)
const int S=1<<21; char ibuf[S],*iS,*iT,obuf[S],*oS=obuf,*oT=oS+S-1;
#define flush() (fwrite(obuf,1,oS-obuf,stdout),oS=obuf,void())
#define getchar() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,S,stdin),(iS==iT?EOF:*iS++)):*iS++)
#define putchar(x) (*oS++=(x),oS==oT?flush():void())
struct Flusher_{~Flusher_(){flush();}}flusher_;
template<class T> inline void read(T &x){
  x=0; register char c=getchar(); register bool f=0;
  while(!isdigit(c))f^=c=='-',c=getchar();
  while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
}
template<class T> inline void print(T x){
  if(x<0)putchar('-'),x=-x;
  if(x>9)print(x/10); putchar(x%10+'0');
}
template<class T> inline void print(T x,char c){print(x),putchar(c);}
const int N=1e5+10,M=1e4+10,S1=256,S2=4;
int n,m,x,blocks,a[N],c[N],bln[N],anc[N],pre[N],siz[N],ans[N];
std::vector<int> G[N];
struct query{
  int l,r,id;
};
std::vector<query> q;
template<class T,int N> struct static_vector{
  T a[N];
  size_t top;
  inline T& operator[](size_t k){return a[k];}
  inline T operator[](size_t k)const{return a[k];}
  inline T& back(){return a[top-1];}
  inline T back()const{return a[top-1];}
  inline void clear(){top=0;}
  inline void pop_back(){top--;}
  inline void push_back(const T &e){a[top++]=e;}
  inline size_t size(){return top;}
};
int mempool[N<<5],*mempointer=mempool;
int* memselect(int n){
  int *res=mempointer;
  log("\e[32mmem select [%d] => %d\e[0m\n",n,res);
  mempointer+=n;
  return res;
}
struct combinable_vector{
  int lim;
  int *l,*r;
  inline size_t size()const{return r-l;}
  inline void clear(){r=l;}
  inline void assign(){l=r=memselect(lim=8);}
  inline void re_assign(){
    int *tl=l,*tr=r;
    lim<<=3,l=memselect(lim),r=l+(tr-tl);
    memcpy(l,tl,size()<<2);
  }
  inline void push_back(int x){if(size()==lim)re_assign(); *(r++)=x;}
  inline void pop_back(){r--;}
  inline void concat(const combinable_vector &rhs){
    if(size()+rhs.size()>lim)re_assign();
    memcpy(r,rhs.l,rhs.size()<<2),r+=rhs.size();
  }
  inline void concat_reverse(const combinable_vector &rhs){r-=rhs.size();}
};
namespace tree{
  int ans,delta,anc[N];
  bool roll,mrk[N];
  std::bitset<M> mem[N/S2+5];
  static_vector<size_t,(N/S2+5)> rub;
  static_vector<std::tuple<int,int,int>,(N<<1)> history;
  struct unicom_block{
    int id,cnt,bitset,key[S2];
    combinable_vector vec;
    inline unicom_block(){bitset=-1,memset(key,-1,sizeof(key)),vec.assign();}
    inline void clear(){
      if(~bitset)mem[bitset].reset(),rub.push_back(bitset),bitset=-1;
      cnt=0,vec.clear(),memset(key,-1,sizeof(key));
    }
    inline void pushup(int k){
      ans-=a[cnt];
      if(~bitset){
        if(mem[bitset][k]){
          mem[bitset][k]=0,--cnt;
        }else{
          mem[bitset][k]=1,++cnt;
        }
      }else{
        for(int i=0;i<S2;i++)if(key[i]==k){key[i]=-1,--cnt; goto out;}
        for(int i=0;i<S2;i++)if(key[i]==-1){key[i]=k,++cnt; goto out;}
        bitset=rub.back(),rub.pop_back();
        mem[bitset][k]=1,++cnt;
        for(int i=0;i<S2;i++)mem[bitset][key[i]]=1;
      }
      out:ans+=a[cnt];
    }
  }uni[N];
  inline void merge(unicom_block &u,unicom_block &v){
    log("\e[31mmerge %d %d\e[0m\n",(int)u.vec.size(),(int)v.vec.size());
    for(int *it=u.vec.l;it!=u.vec.r;it++)v.pushup(*it);
  }
  int find(int x){return x==anc[x]?x:find(anc[x]);}
  void reset(){
    log("\e[2mreset\e[0m\n");
    ans=roll=0;
    for(int i=1;i<=n;i++){
      anc[i]=i;
      if(mrk[i])uni[i].clear(),mrk[i]=0;
    }
    mempointer=mempool;
    for(int i=1;i<=n;i++)uni[i].vec.assign();
  }
  void add(int x){
    log("\e[2madd %d\e[0m\n",x);
    ans+=a[0]; if(roll)delta+=a[0];
    if(roll)history.push_back({0,x,0});
    mrk[x]=1,uni[x].pushup(c[x]);
    uni[x].vec.push_back(c[x]);
    for(int i=0;i<G[x].size();i++)if(mrk[G[x][i]]){
      int y=G[x][i],u=find(x),v=find(y);
      if(uni[u].vec.size()>uni[v].vec.size())std::swap(u,v);
      log("merge %d[%d] %d[%d]\n",x,u,y,v);
      if(roll)history.push_back({u,v,anc[u]});
      merge(uni[u],uni[v]);
      anc[u]=v;
      uni[v].vec.concat(uni[u].vec);
      ans-=a[uni[u].cnt]; if(roll)delta-=a[uni[u].cnt];
    }
  }
  int query(){return ans;}
  void rollback(){
    log("\e[2mrollback\e[0m\n");
    ans-=delta,delta=0;
    for(int u,v,t,i=(int)history.size()-1;i>=0;i--){
      std::tie(u,v,t)=history[i];
      if(u){
        anc[u]=t;
        merge(uni[u],uni[v]);
        uni[v].vec.concat_reverse(uni[u].vec);
      }else{
        mrk[v]=0,uni[v].pushup(c[v]),uni[v].clear();
      }
    }
    history.clear();
  }
}
struct block{
  int id,l,r;
  std::vector<query> q;
  void init(){
    for(int i=l;i<=r;i++)bln[i]=id;
  }
  void solve(){
    std::sort(q.begin(),q.end(),[](const query &a,const query &b){return a.l>b.l;});
    tree::reset();
    int cur=l,i;
    for(const auto &it:q){
      while(it.l<=cur)tree::add(cur--);
      for(tree::roll^=1,i=l+1;i<=it.r;i++)tree::add(i);
      ans[it.id]=tree::query();
      tree::roll^=1,tree::rollback();
    }
  }
}block[S1<<1];
void build(){
  std::function<int(int)> find=[&](int x){return anc[x]==x?x:anc[x]=find(anc[x]);};
  for(int i=1;i<=n;i++)anc[i]=i,siz[i]=1;
  for(int u=1;u<=n;u++){
    for(int v:G[u])if(v<u){
      int fu=find(u),fv=find(v); if(fu==fv)continue;
      if(siz[fu]>siz[fv])std::swap(fu,fv);
      pre[u]+=siz[fu],anc[fu]=fv,siz[fv]+=siz[fu];
    }
    pre[u]+=G[u].size();
  }
  int S=std::accumulate(pre+1,pre+n+1,0)/S1+1;
  fprintf(stderr,"> block limit = %d\n",S);
  std::vector<std::tuple<int,int,int>> seq={{n+1,n,0}};
  for(int i=n;i>=1;i--){
    std::get<0>(seq.back())--,std::get<2>(seq.back())+=pre[i];
    if(i==1||std::get<2>(seq.back())+pre[i]>S)seq.push_back({i,i-1,0});
  }
  seq.pop_back(),std::reverse(seq.begin(),seq.end()),blocks=seq.size();
  for(int _,i=0;i<blocks;i++){
    std::tie(block[i].l,block[i].r,_)=seq[i];
    block[i].id=i,block[i].init();
  }
}
void solve(){
  for(int i=1;i<=n;i++)tree::uni[i].id=i;
  for(const auto &it:q)if(bln[it.l]==bln[it.r]){
    tree::reset();
    for(int i=it.l;i<=it.r;i++)tree::add(i);
    ans[it.id]=tree::query();
  }else{
    block[bln[it.r]].q.push_back(it);
  }
  for(int i=0;i<blocks;i++)block[i].solve();
}
int main(){
  for(int i=0;i<N/S2+5;i++)tree::rub.push_back(i);
#ifdef memset0
  freopen("1.in","r",stdin);
  freopen("1.out","w",stdout);
#endif
  read(n),read(m),read(x);
  for(int i=1;i<=n;i++)read(c[i]),--c[i];
  for(int u,v,i=1;i<n;i++){
    read(u),read(v);
    G[u].push_back(v),G[v].push_back(u);
  }
  for(int i=0;i<=x;i++)read(a[i]);
  build();
  for(int l,r,i=1;i<=m;i++){
    read(l),read(r);
    q.push_back({l,r,i});
  }
  solve();
  for(int i=1;i<=m;i++)print(ans[i],'\n');
  fprintf(stderr,"clocks: %.4lf\n",clock()/(double)CLOCKS_PER_SEC);
}