wo_hen_la @ 2024-07-11 10:44:25
WA了sub#0 6,7,8,9,10,sub#1 1, 不知道哪错了
#include <bits/stdc++.h>
using namespace std;
#define space putchar(' ');
#define enter putchar('\n');
#define pb push_back
#define int long long
#define P 998244353
#define HP 1000000000000002097
#define N (int)2e5+5
int read(){ char ch=getchar();int x=0,f=1;while(ch>'9' || ch<'0'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();return x*f; }
void print(int x){ if(x<0) putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+'0'); }
int n,m,len,cnt;//块长,块的个数
int a[N],loc[N];//每个a[i]所属块的编号
struct Kuai
{
int l,r,tg;//块的左右端点,总和,标记
}k[N];
vector<int> v[N];
void sortt(int x)//对第x个块排序
{
v[x].clear();
for(int i=k[x].l;i<=k[x].r;i++) v[x].pb(a[i]);
sort(v[x].begin(),v[x].end());
}
void modify(int l,int r,int val)
{
int idx=loc[l],idy=loc[r];
if(idx==idy){
for(int i=l;i<=r;i++) a[i]+=val;
sortt(idx);
return;
}
for(int i=l;i<=k[idx].r;i++) a[i]+=val;//左边散块
sortt(idx);
for(int i=k[idy].l;i<=r;i++) a[i]+=val;//右边散块
sortt(idy);
for(int i=idx+1;i<idy;i++) k[i].tg+=val;//整块
}
int query(int l,int r,int val)
{
int idx=loc[l],idy=loc[r],ans=0;
if(idx==idy){
for(int i=l;i<=r;i++) ans+=(a[i]+k[idx].tg>=val);
return ans;
}
for(int i=l;i<=k[idx].r;i++) ans+=(a[i]+k[idx].tg>=val);
for(int i=k[idy].l;i<=r;i++) ans+=(a[i]+k[idy].tg>=val);
for(int i=idx+1;i<idy;i++){
ans+=v[i].end()-lower_bound(v[i].begin(),v[i].end(),val-k[i].tg);
//要减tg的原因是整块修改时不是直接加,而是给tag标记,但是C是算加了tag的,要减去
}
return ans;
}
main()
{
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
cin>>n>>m;
len=sqrtl(n);
for(int i=1;i<=n;i++){
cin>>a[i];
loc[i]=ceil(1.0*i/len);
v[loc[i]].pb(a[i]);
if((i-1)%len==0) k[loc[i]].l=i;
if(i%len==0) k[loc[i]].r=i;
}
cnt=loc[n];
for(int i=1;i<=cnt;i++){
sort(v[i].begin(),v[i].end());
}
char op;
int x,y,z;
while(m--){
cin>>op>>x>>y>>z;
if(x>y) swap(x,y);
if(op=='M') modify(x,y,z);
else cout<<query(x,y,z)<<"\n";
}
return 0;
}
by wo_hen_la @ 2024-07-11 11:08:57
此贴结,数组开太小。
by ZYLZPP @ 2024-07-11 11:12:52
@wo_hen_la
除了数组开小
还要加
k[loc[n]].r = n;
否则
for(int i=k[x].l;i<=k[x].r;i++) v[x].pb(a[i]);
会越界
by wo_hen_la @ 2024-07-11 11:14:07
@ZYLZPP thx.