T1：一个长度为n序列求k小平均值。
区间整体减平均值转化为判断是否为0,这样就等价于前缀和相减了。
大概是因为正负不能通过除正数来转化，因此就不用除长度了。
T2：不会
T3：好题，这题正好把平常的东西反转了一下，因为询问只要求一个和，不能直接回答而要考虑每个更改询问的贡献，
显然我只要查每个当前位置<=x的询问有多少个，也就是l<=p,r>=p,x<=a[p]的l,r,x有多少个，然后可以把询问做主席树，
然后把一个l在位置+1，r在位置-1，这样前缀和（主席树）以后找到的个数正好是左端点在左侧的询问个数，直接统计即可。
平常也可以这么做，把询问离线下来，询问作主席树，然后考虑每个点的贡献。
1 #include<iostream> 2 #include<cstdio> 3 #include<vector> 4 #include<cstring> 5 using namespace std; 6 const int N=100010; 7 int f[N],a[N],s[N],rt[N],tt,cnt; 8 struct tree{int l,r,w;}tr[N*40]; 9 vector<int> qr[N],ql[N]; 10 inline int rd() 11 { 12 int s=0,w=1; 13 char cc=getchar(); 14 for(;cc<‘0‘||cc>‘9‘;cc=getchar()) if(cc==‘-‘) w=-1; 15 for(;cc>=‘0‘&&cc<=‘9‘;cc=getchar()) s=(s<<3)+(s<<1)+cc-‘0‘; 16 return s*w; 17 } 18 void insert(int &k,int x,int l,int r,int w,int d) 19 { 20 k=++tt;tr[k]=tr[x]; 21 if(l==r){tr[k].w+=d;return;} 22 int mid=l+r>>1; 23 if(w<=mid) insert(tr[k].l,tr[x].l,l,mid,w,d); 24 else insert(tr[k].r,tr[x].r,mid+1,r,w,d); 25 tr[k].w=tr[tr[k].l].w+tr[tr[k].r].w; 26 } 27 int ask(int k,int l,int r,int x,int y) 28 { 29 if(l==x&&r==y) return tr[k].w; 30 int mid=l+r>>1; 31 if(y<=mid) return ask(tr[k].l,l,mid,x,y); 32 else if(x>mid) return ask(tr[k].r,mid+1,r,x,y); 33 return ask(tr[k].l,l,mid,x,mid)+ask(tr[k].r,mid+1,r,mid+1,y); 34 } 35 int main() 36 { 37 int n=rd(),m=rd(),qt=rd(),las=0; 38 for(int i=1;i<=n;i++) a[i]=rd(),insert(rt[i],rt[i-1],1,n,a[i],1); 39 for(int i=1;i<=m;i++) 40 { 41 int l=rd(),r=rd(),x=rd(); 42 las+=ask(rt[r],1,n,x,n)-ask(rt[l-1],1,n,x,n); 43 qr[r+1].push_back(x); 44 ql[l].push_back(x); 45 } 46 printf("%d\n",las);tt=0; 47 memset(rt,0,sizeof(rt)); 48 for(int i=1;i<=n+1;i++) 49 { 50 rt[i]=rt[i-1]; 51 for(int j=0;j<qr[i].size();j++) 52 insert(rt[i],rt[i],1,n,qr[i][j],-1); 53 for(int j=0;j<ql[i].size();j++) 54 insert(rt[i],rt[i],1,n,ql[i][j],1); 55 } 56 for(int i=1;i<=qt;i++) 57 { 58 int p=(rd()^las),v=(rd()^las); 59 las+=ask(rt[p],1,n,1,v)-ask(rt[p],1,n,1,a[p]); 60 a[p]=v; 61 printf("%d\n",las); 62 } 63 } 64 /* 65 g++ 1.cpp -o 1 66 ./1 67 4 2 2 68 1 4 2 3 69 2 4 3 70 1 3 2 71 6 6 72 2 7 73 */
原文：https://www.cnblogs.com/starsing/p/11604037.html
