就是这道题,我提交这个代码:
#include<bits/stdc++.h>
using namespace std;
#define ls p<<1
#define rs p<<1|1
inline int read(){
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<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
inline void print(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10^48);
}
const int MAXN=1e5+5;
int n,m,a[MAXN];
struct node{
int w;
}tl[MAXN<<2],tr[MAXN<<2];
void push_up_l(int p){
tl[p].w=tl[ls].w+tl[rs].w;
}
void push_up_r(int p){
tr[p].w=tr[ls].w+tr[rs].w;
}
void modify_l(int l,int r,int pos,int p){
if(l==r){
tl[p].w++;
return;
}
int mid=l+r>>1;
if(pos<=mid)modify_l(l,mid,pos,ls);
if(mid<pos)modify_l(mid+1,r,pos,rs);
push_up_l(p);
}
void modify_r(int l,int r,int pos,int p){
if(l==r){
tr[p].w++;
return;
}
int mid=l+r>>1;
if(pos<=mid)modify_r(l,mid,pos,ls);
if(mid<pos)modify_r(mid+1,r,pos,rs);
push_up_r(p);
}
int query_l(int l,int r,int lq,int rq,int p){
if(lq<=l&&r<=rq)return tl[p].w;
int mid=l+r>>1,sum=0;
if(lq<=mid)sum+=query_l(l,mid,lq,rq,ls);
if(mid<rq)sum+=query_l(mid+1,r,lq,rq,rs);
return sum;
}
int query_r(int l,int r,int lq,int rq,int p){
if(lq<=l&&r<=rq)return tr[p].w;
int mid=l+r>>1,sum=0;
if(lq<=mid)sum+=query_r(l,mid,lq,rq,ls);
if(mid<rq)sum+=query_r(mid+1,r,lq,rq,rs);
return sum;
}
signed main(){
n=read();
int opt,l,r,num,numl,numr;
m=read();
while(m--){
opt=read(),l=read(),r=read();
if(opt==1){
num++;
modify_r(1,n,r,1);
modify_l(1,n,l,1);
}else{
if(l==1)numl=0;
else numl=query_r(1,n,1,l-1,1);
if(r==n)numr=0;
else numr=query_l(1,n,r+1,n,1);
print(num-numl-numr),puts("");
}
}
return 0;
}
开O2之后全WA,然后我就没开,就过了,有dalao能帮忙解释一下吗