suoi 垃圾顯示屏

​​http://www.elijahqi.win/archives/1704​​​

背景

在Z某的家中有一個顯示屏

顯示着班級中船的分布情況

Z某最近在練習“船位預估”技能

是以他會在每天早上做出一些詢問

到晚上再來檢視結果

2017.11.2

Z某的顯示屏被人黑了，軟硬體均有損壞

Z某請你為他維修

描述

支援兩個操作

Q x y表示詢問[1~x][1~y]區間内的船數

C x y表示點(x, y)處增加一條船

輸入

第一行一個整數N

接下來N行，一行一個操作

輸出

對每個詢問，一行一個答案

樣例

輸入

3

Q 1 2

C 1 2

Q 2 2

Copy

輸出

1

Copy

範圍

40% N=10

80% N=

10^3

103

100% N=

10^5+10^5

105+105 1<=x, y<=10000

#include<cstdio>
#define N 220000
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S) {T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0;char ch=gc();
    while(ch<'0'||ch>'9') ch=gc();
    while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();}
    return x;
}
struct node{
    int time,x,y,type;
}query[N],tmp[N];
int s[N],ans[N],n;bool flag[N];
inline void add(int x,int v){
    for (int i=x;i<=1e4;i+=i&(-i)) s[i]+=v;
}
inline void clear(int x){
    for (int i=x;i<=1e4;i+=i&(-i)) if (s[i]) s[i]=0;else return;
}
inline int qr(int x){
    int tt=0;for (int i=x;i;i-=i&(-i)) tt+=s[i];return tt;
}
void cdq(int l,int r){
    if (l==r) return;
    int mid=l+r>>1;cdq(l,mid);cdq(mid+1,r);
    int h1=l,h2=mid+1,op=l;
    while(h1<=mid&&h2<=r){
        if (query[h1].x<query[h2].x||((query[h1].x==query[h2].x)&&query[h1].type<query[h2].type)){      
        if (query[h1].type==1) add(query[h1].y,1);tmp[op++]=query[h1++];}
        else{if (query[h2].type==2) ans[query[h2].time]+=qr(query[h2].y);tmp[op++]=query[h2++];}
    }
    while(h1<=mid) {if (query[h1].type==1) add(query[h1].y,1); tmp[op++]=query[h1++];}
    while(h2<=r) {if (query[h2].type==2) ans[query[h2].time]+=qr(query[h2].y); tmp[op++]=query[h2++];}
    for (int i=l;i<=r;++i) {
        query[i]=tmp[i]; if(query[i].type==1) clear(query[i].y);
    }
}
int main(){
    freopen("a.in","r",stdin);
    n=read();
    for (int i=1;i<=n;++i) {
        char ch=gc();while(ch!='Q'&&ch!='C') ch=gc();query[i].time=i;
        if (ch=='Q') query[i].type=2,flag[i]=1;else query[i].type=1;
        query[i].x=read();query[i].y=read();
    }cdq(1,n); 
    //for (int i=1;i<=n;++i) printf("%d %d %d %d\n",query[i].x,query[i].y,query[i].time,query[i].type);
    for (int i=1;i<=n;++i) if (flag[i]) printf("%d\n",ans[i]);
    return 0;
}