【清华集训2017模拟】Create

本文主要是介绍【清华集训2017模拟】Create，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

这里写图片描述

Input

这里写图片描述

Output

这里写图片描述

Sample Input

5 5 5
1 5 4 1 1
2 5 3
4 5 2
3 5 3
1 2 3
3 5 2
7 1 6
13 12 13
12 14 15
13 13 13
11 12 12

Sample Output

5
9
13
9
9
13

Solution

由于开学军训，导致那么好几天没有来机房，先随便做一题热热身
这题调了我很久
有一种比较显然的方法
他的改变都是区间改变，最简单的做法是线段树
接着要查询的就是一段区间中知道数字是多少，对答案会有多少贡献。那么在线段树中每次找到数值相同的区间，先减去原来数字的贡献，再加上新数字的贡献即可
那么这怎么求呢？
将所有的查询按照数值排序，然后建一棵主席树，对应的数字对应主席树的根，直接查询即可

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define N 101000
#define ll long long
using namespace std;
int a[N],n,m,ac,tot,g[N];
ll ans=0;
struct node{int l,r,x;
}q[N];
struct note{int l,r;ll lz,d;
}t[N*100];
struct USA{int mi,mx,lz;
}f[N*50];
bool cnt(node x,node y){return x.x<y.x;}
void insert(int v,int i,int j,int x,int y)
{if(i==x&&j==y){t[v].lz++;t[v].d+=(j-i+1);return;}int m=(i+j)/2;if(y<=m) t[++tot]=t[t[v].l],t[v].l=tot,insert(t[v].l,i,m,x,y);else if(x>m) t[++tot]=t[t[v].r],t[v].r=tot,insert(t[v].r,m+1,j,x,y);else t[++tot]=t[t[v].l],t[v].l=tot,t[++tot]=t[t[v].r],t[v].r=tot,insert(t[v].l,i,m,x,m),insert(t[v].r,m+1,j,m+1,y);t[v].d=t[t[v].l].d+t[t[v].r].d+t[v].lz*(j-i+1);
}
ll get(int v,int i,int j,int x,int y)
{if(v==0) return 0;if(i==x&&j==y) return t[v].d;int m=(i+j)/2;if(y<=m) return get(t[v].l,i,m,x,y)+t[v].lz*(y-x+1);else if(x>m) return get(t[v].r,m+1,j,x,y)+t[v].lz*(y-x+1);else return get(t[v].l,i,m,x,m)+get(t[v].r,m+1,j,m+1,y)+t[v].lz*(y-x+1);
}
void down(int v)
{if(f[v].lz==0) return;f[v*2].mi=f[v*2].mx=f[v*2].lz=f[v*2+1].mi=f[v*2+1].mx=f[v*2+1].lz=f[v].lz;f[v].lz=0;
}
void change(int v,int i,int j,int x,int y,int z)
{if(i==x&&j==y&&f[v].mi==f[v].mx){ans=ans-get(g[f[v].mi],1,n,i,j);ans=ans+get(g[z],1,n,i,j);f[v].mx=f[v].mi=f[v].lz=z;return;}int m=(i+j)/2;down(v);if(y<=m) change(v*2,i,m,x,y,z);else if(x>m) change(v*2+1,m+1,j,x,y,z);else change(v*2,i,m,x,m,z),change(v*2+1,m+1,j,m+1,y,z);f[v].mi=min(f[v*2].mi,f[v*2+1].mi);f[v].mx=max(f[v*2].mx,f[v*2+1].mx);
}
void read(int &x)
{char ch=getchar();for(;ch<'0'||ch>'9';ch=getchar());x=0;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-48;
}
void readl(ll &x)
{char ch=getchar();for(;ch<'0'||ch>'9';ch=getchar());x=0;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-48;
}
int main()
{freopen("create.in","r",stdin);freopen("create.out","w",stdout);scanf("%d%d%d",&n,&m,&ac);fo(i,1,n) read(a[i]);fo(i,1,m) read(q[i].l),read(q[i].r),read(q[i].x);sort(q+1,q+m+1,cnt);tot=m;fo(i,1,m) t[i]=t[i-1],insert(i,1,n,q[i].l,q[i].r),g[q[i].x]=max(g[q[i].x],i);fo(i,1,n) g[i]=max(g[i],g[i-1]);fo(i,1,n) change(1,1,n,i,i,a[i]);printf("%lld\n",ans);while(ac--){ll x,y,z;readl(x),readl(y),readl(z);x^=ans;y^=ans;z^=ans;change(1,1,n,x,y,z);printf("%lld\n",ans);}
}