题解 P1503 【鬼子进村】

Peipei

上面是我的 Logo >_<

这个我不会用平衡树,线段树之类的搞

我一开始想平衡树了,fhq Treap

但是我是真心没想到怎么操作

根据某白的话

遇事不决先分块

所以 我用的分块啊

简单暴力 而且稳定O(nsqrt(n))

超级棒

#include <bits/stdc++.h>
#define II int
#define IL inline
#define R register
#define I 123456
using namespace std;

IL void of(R II &a) {
    R char c=getchar(); R II w=1,p=0;
    while (c<'0' || c>'9') { if(c=='-') w=-1; c=getchar(); }
    while (c>='0' && c<='9') { p=p*10+c-'0'; c=getchar(); }
    a=p*w; 
}

/* -------------------- Peipei -------------------- */

II Stack[I], had[I], lazy[I], belong[I];

II block,n,m,_top;

IL II Ll(R II x) {
    R II ans=0; 
    while (x>0 && !lazy[x/block]) ans+=min(x,block), x-=block;
    while (x>0 && !had[x]) ans++, x--;
    return ans;
}

IL II Rr(R II x) {
    R II ans=0; if(x==n+1) return 0;
    while (x<=n && !lazy[belong[x]]) ans+=block, x+=block;
    if(x>n+1) ans-=block-(n-n/block*block);
    while (x<=n && !had[x]) ans++, x++;
    return ans;
}

IL II todo(R II x) {
    R II ans=0,l=x,r=x,flag=0;
    if(had[x]) return 0;
    while (l && belong[l]==belong[x]) {
        ans++; l--;
        if(had[l]) { flag=1; break ; }
    }
    if(!flag) ans+=Ll(l);
    flag=0;
    r++;
    while (r<=n && belong[r]==belong[x]) {
        if(had[r]) { flag=1; break ; }
        ans++; r++;
    }
    if(!flag) ans+=Rr(r);
    return ans;
}

int main()
{
//    freopen("1.in","r",stdin);

    of(n); of(m); block=sqrt(n);
    for(R II i=1;i<=n;i++) belong[i]=(i-1)/block+1;
    R char opt; R II x;
    while (m --) {
        cin>> opt; 
        if(opt=='D') {
            of(x); Stack[++_top]=x;
            had[x]=1;
            lazy[belong[x]]++;
        }
        if(opt=='R') {
            x=Stack[_top--];
            had[x]=0;
            lazy[belong[x]]--;
        }
        if(opt=='Q') {
            of(x);
            printf("%d\n",todo(x));
        }
    }
}

根本不用去讲细节实现

裸的分块啦


发表于 2018-01-25 16:35:27 in 题解