拒绝根号，拥抱 ( ext{polylog}) 。
P6108 [Ynoi2009] rprsvq
[ ext{res}=sum_{emptysub Ssubseteq[l,r]}frac{1}{|S|}sum_{a_iin S}(a_i-frac{1}{|S|}sum_{a_iin S}a_i)^2\
=sum_{emptysub Ssubseteq[l,r]}frac{1}{|S|}(sum_{a_iin S}a_i^2-sum_{a_iin S}frac{2a_i}{|S|}sum_{a_iin S}a_i+frac{1}{|S|}(sum_{a_iin S}a_i)^2)\
=sum_{emptysub Ssubseteq[l,r]}frac{1}{|S|}(sum_{a_iin S}a_i^2-frac{1}{|S|}(sum_{a_iin S}a_i)^2)\
= ext{res1}- ext{res2}\
]
为啥我只会卷卷卷来维护啊。
[ ext{res1}=sum_{a_iin[l,r]}sum_{j=0}^{r-l}inom{r-l}{j}frac{a_i^2}{j+1}\
=sum_{j=0}^{r-l}inom{r-l}{j}frac{1}{j+1}sum_{a_iin[l,r]}a_i^2\
=frac{1}{r-l+1}sum_{j=1}^{r-l+1}inom{r-l+1}{j}sum_{a_iin[l,r]}a_i^2\
=frac{1}{r-l+1}(2^{r-l+1}-1)sum_{a_iin[l,r]}a_i^2\
]
[ ext{res2}=sum_{emptysub Ssubseteq[l,r]}(frac{1}{|S|}sum_{a_iin S}a_i)^2\
=sum_{a_iin[l,r]}a_isum_{{a_i}subseteq Ssubseteq[l,r]}frac{1}{|S|^2}sum_{a_jin S}a_j\
=sum_{a_iin[l,r]}a_isum_{j=0}^{r-l}frac{1}{(j+1)^2}(inom{r-l}{j}a_i+sum_{a_kin([l,r]-{a_i})}inom{r-l-1}{j-1}a_k)\
=sum_{a_iin[l,r]}a_isum_{j=0}^{r-l}frac{1}{(j+1)^2}(inom{r-l}{j}a_i+sum_{a_kin([l,r]-{a_i})}(inom{r-l}{j}-inom{r-l-1}{j})a_k)\
=sum_{a_iin[l,r]}a_isum_{j=0}^{r-l}frac{1}{j+1}(sum_{a_kin[l,r]}frac{a_k}{r-l+1}inom{r-l+1}{j+1}-sum_{a_kin([l,r]-{a_i})}frac{a_k}{r-l}inom{r-l}{j+1})\
= ext{res3}- ext{res4}\
]
[ ext{res3}=frac{1}{r-l+1}(sum_{a_iin[l,r]}a_i)^2sum_{j=0}^{r-l}frac{1}{j+1}inom{r-l+1}{j+1}\
]
[ ext{res4}=sum_{a_iin[l,r]}a_isum_{j=0}^{r-l}frac{1}{j+1}sum_{a_kin([l,r]-{a_i})}frac{a_k}{r-l}inom{r-l}{j+1}\
=sum_{a_iin[l,r]}a_isum_{j=0}^{r-l}frac{1}{j+1}(sum_{a_kin[l,r]}frac{a_k}{r-l}inom{r-l}{j+1}-frac{a_i}{r-l}inom{r-l}{j+1})\
= ext{res5}- ext{res6}\
]
[ ext{res5}=frac{1}{r-l}(sum_{a_iin[l,r]}a_i)^2sum_{j=0}^{r-l}frac{1}{j+1}inom{r-l}{j+1}\
]
[ ext{res6}=frac{1}{r-l}sum_{a_iin[l,r]}a_i^2sum_{j=0}^{r-l}frac{1}{j+1}inom{r-l}{j+1}\
]
发现我们需要计算这个式子。
[f(n)=sum_{i=1}^nfrac{1}{i}inom{n}{i}\
f(n+1)=sum_{i=1}^{n+1}frac{1}{i}inom{n+1}{i}\
f(n+1)-f(n)=sum_{i=1}^nfrac{1}{i}inom{n}{i-1}+frac{1}{n+1}inom{n+1}{n+1}\
=frac{1}{n+1}sum_{i=1}^ninom{n+1}{i}+frac{1}{n+1}inom{n+1}{n+1}\
=frac{1}{n+1}sum_{i=1}^{n+1}inom{n+1}{i}\
=frac{2^{n+1}-1}{n+1}\
]
哇哦，做完了啊！！！
#include<bits/stdc++.h>
using namespace std;
const int N=5e6+5;
const int MOD=998244353;
int ADD(int x,int y){return x+y>=MOD?x+y-MOD:x+y;}
int TIME(int x,int y){return (int)(1ll*x*y%MOD);}
int ksm(int x,int k=MOD-2){int res=1;for(;k;k>>=1,x=TIME(x,x))if(k&1)res=TIME(res,x);return res;}
int n,m,f[N];
int C[3][3]={{1,1,1,},{1,2,3},{1,3,6}};
int fact[N],ifact[N],ksm2[N];
int inv(int x){return TIME(ifact[x],fact[x-1]);}
struct Data{int f[3];int &operator [](int x){return f[x];}};
Data operator * (Data f,Data g){
Data res;
memset(res.f,0,sizeof(res.f));
for(int i=0;i<=2;++i){
for(int j=0;j<=2-i;++j)
res[i+j]=ADD(res[i+j],TIME(C[i][j],TIME(f[i],g[j])));
}
return res;
}
Data operator + (Data f,Data g){
Data res;
memset(res.f,0,sizeof(res.f));
for(int i=0;i<=2;++i) res[i]=ADD(f[i],g[i]);
return res;
}
Data fuck(int x){
Data res;
res[0]=1,res[1]=x,res[2]=TIME(x,x);
return res;
}
struct Seg_Tree{
struct Node{Data f;int tag;}tr[N<<2];
void up(int u){tr[u].f=tr[u<<1].f+tr[u<<1|1].f;}
void update(int u,int z){tr[u].f=tr[u].f*fuck(z),tr[u].tag=ADD(tr[u].tag,z);}
void down(int u){update(u<<1,tr[u].tag),update(u<<1|1,tr[u].tag),tr[u].tag=0;}
void build(int u,int l,int r){
if(l==r) return tr[u].f=fuck(0),void();
int mid=(l+r)>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r),up(u);
}
void modify(int u,int l,int r,int x,int y,int z){
if(x<=l&&r<=y) return update(u,z);
int mid=(l+r)>>1;down(u);
if(x<=mid) modify(u<<1,l,mid,x,y,z);
if(y>mid) modify(u<<1|1,mid+1,r,x,y,z);
return up(u);
}
Data query(int u,int l,int r,int x,int y){
if(x<=l&&r<=y) return tr[u].f;
int mid=(l+r)>>1;Data res1,res2;down(u);
if(x<=mid) res1=query(u<<1,l,mid,x,y);
if(y>mid) res2=query(u<<1|1,mid+1,r,x,y);
if(x<=mid&&y>mid) return res1+res2;
return x<=mid?res1:res2;
}
}t;
int main(){
cin>>n>>m;
ksm2[0]=1;for(int i=1;i<=n;++i) ksm2[i]=ADD(ksm2[i-1],ksm2[i-1]);
fact[0]=1;for(int i=1;i<=n;++i) fact[i]=TIME(fact[i-1],i);
ifact[n]=ksm(fact[n]);for(int i=n;i>=1;--i) ifact[i-1]=TIME(ifact[i],i);
for(int i=1;i<=n;++i) f[i]=ADD(f[i-1],TIME(ksm2[i]-1,inv(i)));
t.build(1,1,n);
for(int i=1;i<=m;++i){
int opt,l,r,x;
scanf("%d%d%d",&opt,&l,&r);
if(opt==2){
Data tmp=t.query(1,1,n,l,r);int res=0;
res=ADD(res,TIME(TIME(ksm2[r-l+1]-1,inv(r-l+1)),tmp[2]));
res=ADD(res,MOD-TIME(TIME(f[r-l+1],inv(r-l+1)),TIME(tmp[1],tmp.f[1])));
res=ADD(res,TIME(TIME(f[r-l],inv(r-l)),TIME(tmp[1],tmp[1])));
res=ADD(res,MOD-TIME(TIME(f[r-l],inv(r-l)),tmp[2]));
printf("%d
",res);
}
else scanf("%d",&x),t.modify(1,1,n,l,r,x);
}
return 0;
}
P7880 [Ynoi2006] rldcot
首先如果你被这个 ( ext{dep}) 骗了（像我一样）去搞一些关于树上距离的做法，那你是没有前途的。
题意转化了之后就是区间虚树上点的颜色个数。
你考虑数颜色的题有一个单 (log_2n) 的做法，需要维护每一个颜色最后出现的位置，我们这里就可以这样维护。
那么对于一个点，其会被算在颜色数中要么他就是这段区间的数，要么他的两棵子树中存在点。
我们考虑我们答案的更新实际上只需要找到每一个点在这个 ( ext{lca}) 上的非同一子树的编号最近点即可。实际上我们可以暴力维护这个过程，利用启发式合并的复杂度分析可以知道是 (O(nlog_2^2n)) 的。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=5e5+5;
int n,m;long long c[N];vector<long long> col;
struct Edge{int nxt,to,val;}e[N<<1];int fir[N];
void add(int u,int v,int w,int i){e[i]=(Edge){fir[u],v,w},fir[u]=i;}
struct Query{int l,r,id;}a[M];bool cmp(Query a,Query b){return a.r<b.r;}
vector<pair<int,int> > opt[N];set<int> bag[N];
int get_id(long long c){return lower_bound(col.begin(),col.end(),c)-col.begin()+1;}
void merge(int c,int u,int v){
if(bag[u].size()<bag[v].size()) swap(bag[u],bag[v]);
for(set<int>::iterator i=bag[v].begin(),j;i!=bag[v].end();++i){
j=bag[u].upper_bound(*i);
if(j!=bag[u].end()) opt[*j].push_back(make_pair(c,*i));
j=bag[u].lower_bound(*i);
if(j!=bag[u].begin()) j--,opt[*i].push_back(make_pair(c,*j));
}
while(!bag[v].empty()){
bag[u].insert(*bag[v].begin());
bag[v].erase(bag[v].begin());
}
}
void dfs1(int u,int fa){
for(int i=fir[u];i;i=e[i].nxt){
int v=e[i].to;if(v==fa) continue;
c[v]=c[u]+e[i].val,dfs1(v,u);
}
}
void dfs2(int u,int fa){
for(int i=fir[u];i;i=e[i].nxt){
int v=e[i].to;if(v!=fa) dfs2(v,u);
}
bag[u].insert(u);int tmp=get_id(c[u]);
opt[u].push_back(make_pair(tmp,u));
for(int i=fir[u];i;i=e[i].nxt){
int v=e[i].to;if(v!=fa) merge(tmp,u,v);
}
}
struct Tree_Array{
int tr[N];
int lowbit(int k){return k&(-k);}
void add(int k,int x){for(;k<=n;k+=lowbit(k))tr[k]+=x;}
int sum(int k){int res=0;for(;k;k-=lowbit(k))res+=tr[k];return res;}
}t;
int pos[N],res[M];
int main(){
cin>>n>>m;
for(int i=1;i<n;++i){
int u,v,w;scanf("%d%d%d",&u,&v,&w);
add(u,v,w,i<<1),add(v,u,w,i<<1|1);
}
for(int i=1;i<=m;++i) scanf("%d%d",&a[i].l,&a[i].r),a[i].id=i;
sort(a+1,a+1+m,cmp),dfs1(1,0);
for(int i=1;i<=n;++i) col.push_back(c[i]);
sort(col.begin(),col.end());
col.erase(unique(col.begin(),col.end()),col.end());
dfs2(1,0);int R=0;
for(int i=1;i<=m;++i){
while(R<a[i].r){
++R;
for(int j=0;j<(int)opt[R].size();++j){
pair<int,int> tmp=opt[R][j];
if(pos[tmp.first]) t.add(pos[tmp.first],-1);
pos[tmp.first]=max(pos[tmp.first],tmp.second);
t.add(pos[tmp.first],1);
}
}
res[a[i].id]=t.sum(a[i].r)-t.sum(a[i].l-1);
}
for(int i=1;i<=m;++i) printf("%d
",res[i]);
return 0;
}
/*
这是什么毒瘤题。
原本想从 O(1) lca 的角度去思考，但是发现边权可以是负的。
等一下，如果存在两个点 dep 相同但是点不相同，能否意味着还存在一个 lca ？
好像不太行，因为可能两个点的 lca 的深度是和他们相同的。
--------------------------------------------------------------
或者是我们考虑每一个 lca 的贡献。
但是由于是编号上的询问，我们根本不好搞。
根据不同的深度建虚树？这样会丢失掉点标号的信息。
-------------------------------------------------------------
偷偷看了下题解第一段，意识到自己题目转化错了，是求区间虚树的颜色数。我们再来尝试做
做看。
既然是区间的虚树数颜色，首先每一个点自己会产生贡献。然后他会与区间中的点组合然后再
lca 处做贡献。
首先感觉会有莫队的思路，但是发现我们动态虚树维护是带一个log，所以我们不考虑。
然后数颜色还有一种线段树的搞法，我们考虑这里可不可以实现。
考虑线段树上记录的是当前右端点每一个颜色最后出现的位置。
然后考虑右端点向右移动一位的话，实际上可能会增加很多的位置，这是并不合算的。
我们从单独的 lca 出发，该点的颜色最后一个的位置应该就是倒数第二个的子树。
------------------------------------------------------------------------
思路方向有点对了，但是不知道怎么处理。
实际上每一个点只需要找到其在其祖先中的前驱即可。
我们考虑这个东西的复杂度是什么？实际上我们容易想到树上启发式合并。
然后我们实际上寻找这个前驱的过程可以在启发式合并的过程中搞？
每个点在插入的时候找到前驱后继，更新即可。
NB啊，这是什么神仙题。
*/
P7897 [Ynoi2006] spxmcq
首先我们考虑如果单次询问怎么做，非常轻松的可以得到一个 ( ext{dp}) 式子。
[f_{u}=a_u+x+sum_vmax(f_v,0)
]
我们考虑怎么多次算这个式子。
实际上我们发现，随着 (x) 的增加，(max(f_v,0)) 的取值是单调的，这就启发我们维护一个森林，其中若 (f_vge 0) 则 (e_{u,v}) 连边，这样实际上每一个点的答案就很简单了：
[f_u=a_u+x+sum_vf_v
]
我们此时再来考虑如何得知一个点他此时大于 (0) 了，实际上我们只需要判断其下方所有与之相连的点的权值和与点数乘 (x) 的大小关系即可。然后我们可以利用并查集和优先队列维护这个连边的过程。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,Q=1e6+5;
int n,q;
struct DSU{
int fa[N];
void init(int n){for(int i=1;i<=n;++i)fa[i]=i;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
}d;
struct Node{long long siz,sum;int id;}tr[N];
bool operator > (Node a,Node b){return (-a.sum)*b.siz>(-b.sum)*a.siz;}
bool operator != (Node a,Node b){return a.siz!=b.siz||a.sum!=b.sum;}
struct Query{int u,x,id;}a[Q];
bool cmp(Query a,Query b){return a.x<b.x;}
long long res[Q];
priority_queue<Node,vector<Node>,greater<Node> > pq;
struct Tree_Array{
long long tr[N];
int lowbit(int k){return k&(-k);}
void add(int k,long long x){for(;k&&k<=n;k+=lowbit(k))tr[k]+=x;}
long long sum(int k){long long res=0;for(;k;k-=lowbit(k))res+=tr[k];return res;}
}t1,t2;
int fa[N],L[N],R[N],cnt_dfn;
struct Edge{int nxt,to;}e[N];int fir[N];
void add(int u,int v,int i){e[i]=(Edge){fir[u],v},fir[u]=i;}
void dfs(int u){
L[u]=++cnt_dfn;
for(int i=fir[u];i;i=e[i].nxt) dfs(e[i].to);
R[u]=cnt_dfn;
}
int main(){
cin>>n>>q,d.init(n);
for(int i=2;i<=n;++i) scanf("%d",&fa[i]),add(fa[i],i,i);
for(int i=1;i<=n;++i) scanf("%lld",&tr[i].sum),tr[i].siz=1,tr[i].id=i;
for(int i=1;i<=q;++i) scanf("%d%d",&a[i].u,&a[i].x),a[i].id=i;
sort(a+1,a+1+q,cmp),dfs(1);
for(int i=1;i<=n;++i){
t1.add(L[i],tr[i].siz),t1.add(L[fa[i]],-tr[i].siz);
t2.add(L[i],tr[i].sum),t2.add(L[fa[i]],-tr[i].sum);
}
for(int i=1;i<=n;++i) pq.push(tr[i]);
for(int i=1;i<=q;++i){
while(!pq.empty()){
if(pq.top()!=tr[pq.top().id]){pq.pop();continue;}
if(pq.top().sum+pq.top().siz*a[i].x<0) break;
Node u=pq.top();pq.pop();
if(fa[u.id]){
int fu=d.find(fa[u.id]),fv=d.find(u.id);d.fa[fv]=fu;
tr[fu].siz+=tr[fv].siz,tr[fu].sum+=tr[fv].sum,pq.push(tr[fu]);
t1.add(L[fa[fv]],tr[fv].siz),t1.add(L[fa[fu]],-tr[fv].siz);
t2.add(L[fa[fv]],tr[fv].sum),t2.add(L[fa[fu]],-tr[fv].sum);
}
}
long long tmp1=t1.sum(R[a[i].u])-t1.sum(L[a[i].u]-1);
long long tmp2=t2.sum(R[a[i].u])-t2.sum(L[a[i].u]-1);
res[a[i].id]=a[i].x*tmp1+tmp2;
}
for(int i=1;i<=q;++i) printf("%lld
",res[i]);
return 0;
}
/*
我们首先考虑没有修改的单次询问怎么做。
首先如果是一个区间序列的话，实际上就是一个贪心的过程。
我们意识到还有一个在线段树上的做法。
我们考虑这个线段树上的做法。由于是要强制包含子树的根节点的，实际上就是所有子树的
答案加起来加上自己的权值。这本质上和区间的做法是一样的，
我们再考虑修改怎么搞，我想考虑搞一个关于 x 的分段函数。
膜拜 dpair ，数据结构之神！！！！
我们考虑到每一个点的贡献实际上就是一段斜线，我们考虑转化成差分数组之后线段树合并。
但是我是值域线段树，不会搞了。
------------------------------------------------------------------------
我们考虑离线之后按 x 排序，然后对于 $max(f_v,0)$ 这个转移实际上取值是单调的，我
们就考虑暴力维护每一个点的转移时间，我们考虑到这与其 siz 和 sum 有关。
但是注意到，已经连接的我们已经不需要维护了，我们只需要维护最上面的一个点的 siz 和
sum 即可，所以暴力用并查集来搞就行了。
*/
P6018 [Ynoi2010] Fusion tree
首先这题有一个 ( ext{trick}) ，就是每一个节点只统计孩子的贡献，然后父亲的贡献是可以直接算的。
我们就考虑如何维护孩子权值的异或和，同时需要进行全局加 (1) 。
你会意识到全局加一在二进制下就是最低位的 (0) 变成 (1) ，然后比其低的 (1) 变成 (0) 。我们发现如果我们倒建 ( ext{trie}) 树是可以轻松维护的。
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,a[N],b[N],fa[N];
struct Edge{int nxt,to;}e[N<<1];int fir[N];
void add(int u,int v,int i){e[i]=(Edge){fir[u],v},fir[u]=i;}
void dfs(int u){
for(int i=fir[u];i;i=e[i].nxt)
if(e[i].to!=fa[u]) fa[e[i].to]=u,dfs(e[i].to);
}
struct Trie{
int rt[N],tot;
struct Node{int data,siz,son[2];}tr[N*22];
void up(int u,int k){
tr[u].data=(tr[tr[u].son[0]].data^tr[tr[u].son[1]].data);
tr[u].data|=(1<<k)*tr[tr[u].son[1]].siz;
}
void insert(int &u,int k,int x){
if(!u) u=++tot;
tr[u].siz^=1;if(k>=20) return ;
insert(tr[u].son[(x>>k)&1],k+1,x),up(u,k);
}
void opt(int u,int k){
if(k>=20) return ;
swap(tr[u].son[0],tr[u].son[1]);
opt(tr[u].son[0],k+1),up(u,k);
}
}t;
int main(){
cin>>n>>m;
for(int i=1;i<n;++i){
int u,v;scanf("%d%d",&u,&v);
add(u,v,i<<1),add(v,u,i<<1|1);
}
dfs(1);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) if(fa[i]) t.insert(t.rt[fa[i]],0,a[i]);
for(int i=1;i<=m;++i){
int opt,u;scanf("%d%d",&opt,&u);
if(opt==2){
int x;scanf("%d",&x);
if(fa[u]) t.insert(t.rt[fa[u]],0,a[u]+b[fa[u]]);
a[u]-=x;if(fa[u]) t.insert(t.rt[fa[u]],0,a[u]+b[fa[u]]);
}
else if(opt==1){
if(fa[u]){
if(fa[fa[u]]) t.insert(t.rt[fa[fa[u]]],0,a[fa[u]]+b[fa[fa[u]]]);
a[fa[u]]++;if(fa[fa[u]]) t.insert(t.rt[fa[fa[u]]],0,a[fa[u]]+b[fa[fa[u]]]);
}
b[u]++,t.opt(t.rt[u],0);
}
else printf("%d
",t.tr[t.rt[u]].data^(a[fa[u]]+b[fa[fa[u]]]));
}
}
/*
距离为 $1$ 的点的权值异或和。这是啥。。。
我们能否考虑只维护异或和？感觉有点不太可行。
--------------------------------------------------------------------------
你考虑每一次加一，实际上是在干嘛，就是将最低位的 $0$ 变成 $1$ 然后比其低的 $1$ 变
成 $0$ 。你发现这个东西我们可以建一个反向 $trie$ 来维护，然后做完了。
*/