rt,题解中没有看到,不知道是否可行:
在查询 [l,r] 的时候,用总的地雷种数 减去 [1,l−1] 的地雷总数再减去 [r+1,n]的地雷总数,即
ans=cnt-query(1,l-1)-query(r+1,n)
(与代码格式略有出入)
实测有些问题(样例没过,输出两个1),可能是自己代码的问题(那就求调吧)
上代码:
#include <iostream>
using namespace std;
inline int lc(int p){return p<<1;}
inline int rc(int p){return p<<1|1;}
const int Maxn=1e5+2e4;
int n,m;
int sum[2][Maxn*4];
void pushup(int p,int c)
{
sum[c][p]=sum[c][lc(p)]+sum[c][rc(p)];
}
void modify(int p,int l,int r,int c,int x)
{
if(l==r)
{
sum[c][x]++;
return;
}
int mid=(l+r)>>1;
if(x<=mid) modify(lc(p),l,mid,c,x);
else modify(rc(p),mid+1,r,c,x);
pushup(p,c);
}
int query(int p,int l,int r,int c,int ql,int qr)
{
if(ql<=l&&r<=qr) return sum[c][p];
int mid=(l+r)>>1,res=0;
if(ql<=mid) res+=query(lc(p),l,mid,c,ql,qr);
if(mid<qr) res+=query(rc(p),mid+1,r,c,ql,qr);
return res;
}
int main()
{
int cnt=0;
scanf("%d%d",&n,&m);
int op,x,y;
while(m--)
{
scanf("%d%d%d",&op,&x,&y);
if(op==1)
{
++cnt;
modify(1,1,n,0,x);
modify(1,1,n,1,y+1);
}
else
{
int ans=cnt;
if(y<n) ans-=query(1,1,n,0,y+1,n);
if(x>1) ans-=query(1,1,n,1,1,x-1);
printf("%d\n",ans);
}
}
}