题解 P1503 【鬼子进村】

平衡树过的是一般大佬，暴力过的才是局佬数据太水了然鹅我用树状数组+二分过，复杂度$（n*logn^2）$ 树状数组好房子打1,坏房子打0 对于每次Q，分别往左右二分（用树状数组check中间是否有断点），最远段点求距离就行了还要注意输入的时候小心处理（用cin最好，自己getchar容错性太低）下面是AC代码

#include<bits/stdc++.h>
#define lowbit(x) (x&-x)
#define sum(l,r) (ask(r)-ask(l-1))
using namespace std;

int read() {
    register int x=1,ans=0;register char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') x*=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {ans=(ans<<3)+(ans<<1)+ch-48;ch=getchar();}
    return x*ans;
}

const int N=50005;
int c[N],n,m;

void add(int x,int val) {
    for(;x<=n;x+=lowbit(x)) c[x]+=val;
}

int ask(int x) {
    int ans=0;
    for(;x>=1;x-=lowbit(x)) ans+=c[x];
    return ans;
}

int main() {
    n=read(); m=read();
    for(register int i=1;i<=n;++i) add(i,1);
    stack<int> w;
    while(m--) {
        char ch; cin>>ch;
        if(ch=='D') {
            int x=read(); 
            add(x,-1);
            w.push(x);
        }
        else if(ch=='R') {
            int x=w.top(); w.pop(); add(x,1);
        } 
        else {
            int x=read(); 
            if(sum(x,x)==0) puts("0");
            else {
                int l=1,r=x,res=0;
                while(l<=r) {
                    int mid=(l+r)>>1;
                    if(sum(mid,x)==x-mid+1) res=mid,r=mid-1;
                    else l=mid+1;
                }
                int ll=res;
                l=x,r=n;
                while(l<=r) {
                    int mid=(l+r)>>1;
                    if(sum(x,mid)==mid-x+1) res=mid,l=mid+1;
                    else r=mid-1;
                }
                int rr=res;
                printf("%dn",rr-ll+1);
            }
        }
    }
    return 0;
}

题解 P1503 【鬼子进村】

搜索

归档

标签

最新文章