# bzoj 2989: 数列&4170: 极光

### 题解：

code：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
struct node{
int op,x,y,c;
}q[1500000],tmp[1500000];int cnt=0,qcnt=0,Q[1500000],tr[2000010];
int n,m,a[400010],ans[100010];
void add(int op,int X,int Y,int c) {q[++cnt].op=op;q[cnt].x=X-Y;q[cnt].y=X+Y;q[cnt].c=c;}
int lowbit(int x) {return x&(-x);}
void change(int k,int c) {k=max(k,0);k++;for(int i=k;i<=2000001;i+=lowbit(i)) tr[i]+=c;}
void rechange(int k) {k=max(k,0);k++;for(int i=k;i<=2000001;i+=lowbit(i)) tr[i]=0;}
int get(int k) {k++;int ANS=0;for(int i=k;i>=1;i-=lowbit(i)) ANS+=tr[i];return ANS;}
{
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<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
void cdq(int l,int r)
{
if(l==r) return;
int mid=(l+r)/2;
cdq(l,mid);cdq(mid+1,r);
int i=l,j=mid+1,len=0,st=0;
while(i<=mid&&j<=r)
{
if(q[i].x<=q[j].x)
{
if(q[i].op==1) change(q[i].y,1),Q[++st]=q[i].y;
tmp[++len]=q[i++];
}
else
{
if(q[j].y<0) {tmp[++len]=q[j++];continue;}
int num=get(q[j].y);
if(q[j].op==2) ans[q[j].c]+=num;
else ans[q[j].c]-=num;
tmp[++len]=q[j++];
}
}
while(i<=mid) tmp[++len]=q[i++];
while(j<=r)
{
if(q[j].y<0) {tmp[++len]=q[j++];continue;}
int num=get(q[j].y);
if(q[j].op==2) ans[q[j].c]+=num;
else ans[q[j].c]-=num;
tmp[++len]=q[j++];
}
for(i=1;i<=len;i++) q[l+i-1]=tmp[i];
for(i=1;i<=st;i++) rechange(Q[i]);
}
int main()
{
for(int i=1;i<=n;i++)
{
}
char s[10];
for(int i=1;i<=m;i++)
{
scanf("%s",s+1);
if(s[1]=='M')
{
}
else
{
}