T1: 一个长度为 n 序列求 k 小平均值.
区间整体减平均值转化为判断是否为 0, 这样就等价于前缀和相减了.
大概是因为正负不能通过除正数来转化, 因此就不用除长度了.
T2: 不会
T3: 好题, 这题正好把平常的东西反转了一下, 因为询问只要求一个和, 不能直接回答而要考虑每个更改询问的贡献,
显然我只要查每个当前位置 <=x 的询问有多少个, 也就是 l<=p,r>=p,x<=a[p] 的 l,r,x 有多少个, 然后可以把询问做主席树,
然后把一个 l 在位置 + 1,r 在位置 - 1, 这样前缀和 (主席树) 以后找到的个数正好是左端点在左侧的询问个数, 直接统计即可.
平常也可以这么做, 把询问离线下来, 询问作主席树, 然后考虑每个点的贡献.
- #include<iostream>
- #include<cstdio>
- #include<vector>
- #include<cstring>
- using namespace std;
- const int N=100010;
- int f[N],a[N],s[N],rt[N],tt,cnt;
- struct tree{int l,r,w;}tr[N*40];
- vector<int> qr[N],ql[N];
- inline int rd()
- {
- int s=0,w=1;
- char cc=getchar();
- for(;cc<'0'||cc>'9';cc=getchar()) if(cc=='-') w=-1;
- for(;cc>='0'&&cc<='9';cc=getchar()) s=(s<<3)+(s<<1)+cc-'0';
- return s*w;
- }
- void insert(int &k,int x,int l,int r,int w,int d)
- {
- k=++tt;tr[k]=tr[x];
- if(l==r){tr[k].w+=d;return;}
- int mid=l+r>>1;
- if(w<=mid) insert(tr[k].l,tr[x].l,l,mid,w,d);
- else insert(tr[k].r,tr[x].r,mid+1,r,w,d);
- tr[k].w=tr[tr[k].l].w+tr[tr[k].r].w;
- }
- int ask(int k,int l,int r,int x,int y)
- {
- if(l==x&&r==y) return tr[k].w;
- int mid=l+r>>1;
- if(y<=mid) return ask(tr[k].l,l,mid,x,y);
- else if(x>mid) return ask(tr[k].r,mid+1,r,x,y);
- return ask(tr[k].l,l,mid,x,mid)+ask(tr[k].r,mid+1,r,mid+1,y);
- }
- int main()
- {
- int n=rd(),m=rd(),qt=rd(),las=0;
- for(int i=1;i<=n;i++) a[i]=rd(),insert(rt[i],rt[i-1],1,n,a[i],1);
- for(int i=1;i<=m;i++)
- {
- int l=rd(),r=rd(),x=rd();
- las+=ask(rt[r],1,n,x,n)-ask(rt[l-1],1,n,x,n);
- qr[r+1].push_back(x);
- ql[l].push_back(x);
- }
- printf("%d\n",las);tt=0;
- memset(rt,0,sizeof(rt));
- for(int i=1;i<=n+1;i++)
- {
- rt[i]=rt[i-1];
- for(int j=0;j<qr[i].size();j++)
- insert(rt[i],rt[i],1,n,qr[i][j],-1);
- for(int j=0;j<ql[i].size();j++)
- insert(rt[i],rt[i],1,n,ql[i][j],1);
- }
- for(int i=1;i<=qt;i++)
- {
- int p=(rd()^las),v=(rd()^las);
- las+=ask(rt[p],1,n,1,v)-ask(rt[p],1,n,1,a[p]);
- a[p]=v;
- printf("%d\n",las);
- }
- }
- /*
- g++ 1.cpp -o 1
- ./1
- 4 2 2
- 1 4 2 3
- 2 4 3
- 1 3 2
- 6 6
- 2 7
- */
- View Code
来源: http://www.bubuko.com/infodetail-3217070.html