Description
Solution
树状数组套线段树。
树状数组代表a的大小。对于树状数组上某个点i(代表的a的区间[A,B]),rk[i]是节点i上以1-n为下标建立的线段树根节点，线段树中代表区间[L,R]的节点的权值为f[L]到f[R]的所有项的总和中，次数在[A,B]范围内的个数。
PS:题目钦定答案>=1，所以所有ci可以不用管。
Code
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; typedef long long ll; const int N=10000010; int n,m; struct Seg { int lc[N],rc[N],tag[N],tot=0;ll sum[N]; void pushdown(int k,int l,int r) { int mid=(l+r)/2; if (!lc[k]) lc[k]=++tot; if (!rc[k]) rc[k]=++tot; sum[lc[k]]+=tag[k]*(mid-l+1);sum[rc[k]]+=tag[k]*(r-mid); tag[lc[k]]+=tag[k];tag[rc[k]]+=tag[k]; tag[k]=0; } void add(int &k,int l,int r,int askx,int asky) { if (!k) k=++tot; if (askx<=l&&r<=asky) {tag[k]++;sum[k]+=r-l+1;return;} int mid=(l+r)/2; pushdown(k,l,r); if (askx<=mid) add(lc[k],l,mid,askx,asky); if (asky>mid) add(rc[k],mid+1,r,askx,asky); sum[k]=sum[lc[k]]+sum[rc[k]]; } ll query(int k,int l,int r,int askx,int asky) { if (!k) return 0; if (askx<=l&&r<=asky) return sum[k]; pushdown(k,l,r); int mid=(l+r)/2;ll re=0; if (askx<=mid) re+=query(lc[k],l,mid,askx,asky); if (asky>mid) re+=query(rc[k],mid+1,r,askx,asky); return re; } }seg; int rt[1000010],len=1e6; void add(int l,int r,int x){for(;x<=len;x+=x&-x) seg.add(rt[x],1,n,l,r);} int query(int l,int r,ll x) { ll s=0,v;int k,ans=0; for(k=len;k;k-=k&-k) s+=seg.query(rt[k],1,n,l,r); x=s-x; if (x<=0){printf("1 %lld ",s);return 1;} for(k=1;k<<1<=len;k<<=1); for(;k;k>>=1) if (ans+k<=len) { v=seg.query(rt[k+ans],1,n,l,r); if (x>v){x-=v;ans+=k;} } ans+=2; for(k=ans-1,v=0;k;k-=k&-k) v+=seg.query(rt[k],1,n,l,r); printf("%d %lld ",ans,s-v); return ans; } int t,l,r,lastp=0;ll x; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&t); for (int i=1;i<=m;i++) { scanf("%d%d%d%lld",&t,&l,&r,&x); if (t==0) x^=lastp,add(l,r,x); else lastp=query(l,r,x); } }