BZOJ3091城市旅行——LCT区间信息合并-白红宇

BZOJ3091城市旅行——LCT区间信息合并

阅读量：6580 次

发布时间：2019-06-24

本文共 3377 字，大约阅读时间需要 11 分钟。

题目描述

输入

输出

样例输入

4 5

1 3 2 5

1 2

1 3

2 4

4 2 4

1 2 4

2 3 4

3 1 4 1

4 1 4

样例输出

16/3

6/1

提示

对于所有数据满足 1<=N<=50,000 1<=M<=50,000 1<=Ai<=10^6 1<=D<=100 1<=U,V<=N

前三个操作都很简单了，LCT就能维护，重点是第四个操作。

求一个区间所有子区间的区间和之和，直接求所有区间和不好求，我们换一种角度去做。

考虑每个点对区间的贡献，假设当前区间是[l,r]，对于区间中的点k(l<=k<=r)，它的贡献就是它的点权*(k-l+1)*(r-k+1)。

那么我们维护区间答案，考虑怎么上传及修改？

先说上传，就是将一个点的左儿子区间+这个点+这个点的右儿子区间合并。

我们设size[x]为x子树大小，也就是x子树所代表的区间的长度；ls代表左子树，rs代表右子树。

对于左区间，每个点的贡献要加上它从左往右数的排名*它的点权*(1+size[rs])。

对于右区间，每个点的贡献要加上它从右往左数的排名*它的点权*(1+size[ls])。

对于点x要加上它的点权*(1+size[ls])*(1+size[rs])。

发现排名*点权的和无法直接求，因此还要维护两个信息lv[x],rv[x]，分别代表x子树所代表区间中每个点点权*从左/从右排名的和。

再看看这两个信息怎么合并，就以lv[x]为例吧，先将左右子节点的lv加上，左子树lv不变，右子树的lv发现每个点排名都加了(1+size[ls])，只要再加上右子树权值和*(1+size[ls])就好了。

综上所述，我们需要维护六个变量val,sum,lv,rv,size,ans，分别代表单点权值、子树权值和、点权*从左数排名之和、点权*从右数排名之和、子树节点数、区间所有子区间和之和即答案。

再说怎么修改？设n代表区间长,v为修改时的增量

val和sum比较常规在这就不说了。

lv和rv都加了 $v*\sum_{i=1}^{n}i=v*\frac{n*(n+1)}{2}$

而ans则加了 $v*\sum_{i=1}^{n}\sum_{j=1}^{i}j=v*\sum_{i=1}^{n}\frac{i*(i+1)}{2}=v*\frac{n*(n+1)*(n+2)}{6}$

最后这个推一个通项公式就好了。

知道怎么上传和修改后剩下的就LCT基本操作了。

但要注意翻转时也要把lv和rv交换且旋到原树根的操作splay之后不能只打标记，要先把当前点左右子树翻转，否则当前点的lv和rv是反的。

#include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define ll long long#define ls s[rt][0]#define rs s[rt][1]using namespace std;int n,m;int x,y;int opt;ll z;int r[50010];int s[50010][2];int f[50010];int st[50010];ll lv[50010];ll rv[50010];ll sum[50010];ll size[50010];ll val[50010];ll ans[50010];ll a[50010];ll p,q;ll res;int get(int rt){ return s[f[rt]][1]==rt;}int is_root(int rt){ return s[f[rt]][1]!=rt&&s[f[rt]][0]!=rt;}void add(int rt,ll v){ val[rt]+=v; sum[rt]+=v*size[rt]; lv[rt]+=v*size[rt]*(size[rt]+1)/2; rv[rt]+=v*size[rt]*(size[rt]+1)/2; ans[rt]+=v*size[rt]*(size[rt]+1)*(size[rt]+2)/6; a[rt]+=v;}void flip(int rt){ swap(ls,rs); swap(lv[rt],rv[rt]); r[rt]^=1;}void pushup(int rt){ size[rt]=size[ls]+size[rs]+1; sum[rt]=sum[ls]+sum[rs]+val[rt]; lv[rt]=lv[ls]+lv[rs]+(val[rt]+sum[rs])*(size[ls]+1); rv[rt]=rv[ls]+rv[rs]+(val[rt]+sum[ls])*(size[rs]+1); ans[rt]=ans[ls]+ans[rs]+val[rt]*(size[ls]+1)*(size[rs]+1)+lv[ls]*(size[rs]+1)+rv[rs]*(size[ls]+1);}void pushdown(int rt){ if(r[rt]) { r[rt]^=1; flip(ls); flip(rs); } if(a[rt]) { add(ls,a[rt]); add(rs,a[rt]); a[rt]=0; }}void rotate(int rt){ int fa=f[rt]; int anc=f[fa]; int k=get(rt); if(!is_root(fa)) { s[anc][get(fa)]=rt; } s[fa][k]=s[rt][k^1]; f[s[fa][k]]=fa; s[rt][k^1]=fa; f[fa]=rt; f[rt]=anc; pushup(fa); pushup(rt);}void splay(int rt){ int top=0; st[++top]=rt; for(int i=rt;!is_root(i);i=f[i]) { st[++top]=f[i]; } for(int i=top;i>=1;i--) { pushdown(st[i]); } for(int fa;!is_root(rt);rotate(rt)) { if(!is_root(fa=f[rt])) { rotate(get(fa)==get(rt)?fa:rt); } }}void access(int rt){ for(int x=0;rt;x=rt,rt=f[rt]) { splay(rt); s[rt][1]=x; pushup(rt); }}void reverse(int rt){ access(rt); splay(rt); flip(rt);}void link(int x,int y){ reverse(x); f[x]=y;}void cut(int x,int y){ reverse(x); access(y); splay(y); if(s[x][1]||f[x]!=y) { return ; } s[y][0]=f[x]=0; pushup(y);}void change(int x,int y,ll z){ reverse(x); access(y); splay(y); add(y,z);}int find(int rt){ while(f[rt]) { rt=f[rt]; } return rt;}void split(int x,int y){ reverse(x); access(y); splay(y);}ll gcd(ll x,ll y){ if(y==0) { return x; } return gcd(y,x%y);}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%lld",&val[i]); pushup(i); } for(int i=1;i

转载于:https://www.cnblogs.com/Khada-Jhin/p/9748300.html

你可能感兴趣的文章