分块之后，一定要注意你操作之后的数组并不是修改的区间！
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define fi first #define se second #define pb push_back #define mp std::make_pair #define ulf Useful_little_function #define abs ccf #define INF (0x3f3f3f3f) #define INT_INF (2147483647) #define LLINF (0x3f3f3f3f3f3f3f3fll) #define LL_INF (9223372036854775807) #define memset __builtin_memset #define popcount __builtin_popcount std::mt19937 rnd(std::chrono::system_clock::now().time_since_epoch().count()); typedef long long ll; typedef std::pair pii; typedef unsigned int uint; typedef unsigned long long ull; inline void file(){freopen(".in","r",stdin);freopen(".out","w",stdout);} namespace IO{ #define BUF_SIZE (1<<16) #define OUT_SIZE (1<<16) bool IOerror=0; inline char nc(){static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;if(p1==pend){p1=buf;pend=buf+fread(buf,1,BUF_SIZE,stdin);if(pend==p1)return IOerror=1,-1;}return *p1++;} inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';} inline void read(int &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(sign)x=-x;} inline void read(ll &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(sign)x=-x;} inline void read(double &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(ch=='.'){double tmp=1;ch=nc();for(;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');}if(sign)x=-x;} inline void read(char *s){char ch=nc();for(;blank(ch);ch=nc());if(IOerror)return;for(;!blank(ch)&&!IOerror;ch=nc())*s++=ch;*s=0;} inline void read(char &c){for(c=nc();blank(c);c=nc());if(IOerror){c=-1;return;}} struct Ostream_fwrite{ char *buf,*p1,*pend; Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;} inline void out(char ch){if(p1==pend){fwrite(buf,1,BUF_SIZE,stdout);p1=buf;}*p1++=ch;} inline void print(int x){static char s[15],*s1;s1=s;if(!x)*s1++='0';if(x<0)out('-'),x=-x;while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);} inline void println(int x){print(x);out('\n');} inline void print(ll x){static char s[25],*s1;s1=s;if(!x)*s1++='0';if(x<0)out('-'),x=-x;while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);} inline void println(ll x){print(x);out('\n');} inline void print(double x,int y){//y<18 static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL}; if(x<-1e-12)out('-'),x=-x;x*=mul[y];ll x1=(ll)floor(x);if(x-floor(x)>=0.5)++x1;ll x2=x1/mul[y],x3=x1-x2*mul[y];print(x2);if(y>0){out('.');for(size_t i=1;ib?a:b;} inline ll max(const ll &a,const ll &b){return a>b?a:b;} inline double max(const double &a,const double &b){return a>b?a:b;} inline int min(const int &a,const int &b){return aa)a=b;} inline void chkmax(ll &a,const ll &b){if(b>a)a=b;} inline void chkmax(double &a,const double &b){if(b>a)a=b;} inline void chkmin(int &a,const int &b){if(b=mod?x-mod:x;} inline int madd(const int &x,const int &y){return x+y>=1,a=(ll)a*a%mod)if(k&1)s=(ll)s*a%mod;return s;} inline void _init(int n){ ni[1]=1; for(int i=2;i<=n;++i) ni[i]=mod-(ll)ni[mod%i]*(mod/i)%mod; mul[0]=invmul[0]=1; for(int i=1;i<=n;++i) mul[i]=(ll)mul[i-1]*i%mod; invmul[n]=qpow(mul[n],mod-2); for(int i=n-1;i;--i) invmul[i]=(ll)invmul[i+1]*(i+1)%mod; } inline int C(int n,int m){if(m>n)return 0;return (ll)mul[n]*invmul[m]%mod*invmul[n-m]%mod;} #undef N } const int N=1e6+13,SqN=3000+13; struct Block{int a[SqN],tag;}s[SqN]; int n,q,m,b[N],from[N],L[SqN],R[SqN]; int main(){ #ifdef LOCAL freopen("ex_p2.in","r",stdin); freopen("a.out","w",stdout); #endif read(n),read(q);int tt=1000; for(int i=1;i<=n;++i) read(b[i]); L[m=1]=1; for(int i=1;i<=n;++i){ from[i]=m; if(i%tt==0){ R[m]=i; if(i=x); println(ans); } else{ int ans=0,p=from[l]; for(int i=l;i<=R[p];++i) ans+=(b[i]+s[p].tag>=x); p=from[r]; for(int i=L[p];i<=r;++i) ans+=(b[i]+s[p].tag>=x); for(int i=from[l]+1;i>1; if(s[i].a[mid]>=val) _r=mid; else _l=mid+1; } ans+=(R[i]-L[i]+1-_l+1); } println(ans); } } } return 0; }