给出一个长为n的数列,以及n个操作,操作涉及区间加法,询问区间内小于某个值x的元素个数。
code:
#include#include #include #include #include #include #define ll long longusing namespace std;int rd() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar();} return x*f;}const int MAX=50010;int n,blo;int v[MAX],tag[MAX],bl[MAX];vector vec[505];void reset(int x) { vec[x].clear(); for(int i=(x-1)*blo+1;i<=min(x*blo,n);i++) vec[x].push_back(v[i]); sort(vec[x].begin(),vec[x].end());}void add(int a,int b,int c) { for(int i=a;i<=min(bl[a]*blo,b);i++) v[i]+=c; reset(bl[a]); if(bl[a]!=bl[b]) { for(int i=(bl[b]-1)*blo+1;i<=b;i++) v[i]+=c; reset(bl[b]); } for(int i=bl[a]+1;i<=bl[b]-1;i++) tag[i]+=c;}int query(int l,int r,int c) { int ans=0; for(int i=l;i<=min(bl[l]*blo,r);i++) if(v[i]+tag[bl[l]]