http://www.lydsy.com/JudgeOnline/problem.php?id=1493

Brief description:

略。）

Analysis:

测试模板。）

//}/* .................................................................................................................................. */
 
const int MAXN=500001;
 
const int N = int(5e5) + 9, NN = 4*N;
 
int n;
 
namespace T{
 
    int lc[NN], rc[NN], sc[NN]; bool s0[NN];
    int a, b, c;
 
#define lx (x<<1)
#define rx (lx|1)
#define ml (l+r>>1)
#define mr (ml+1)
#define lcc lx,l,ml
#define rcc rx,mr,r
#define rt 1, 0, n-1
 
    void sss(int x, int c){
        lc[x] = rc[x] = c;
        sc[x] = s0[x] = 1;
    }
 
    void upd(int x){
        lc[x] = lc[lx]; rc[x] = rc[rx];
        sc[x] = sc[lx] + sc[rx] - (rc[lx] == lc[rx]);
    }
 
    void rls(int x){
        if (s0[x]){
            sss(lx, lc[x]), sss(rx, rc[x]);
            s0[x] = 0;
        }
    }
 
    int getColor(int x, int l, int r){
        if (l == r) return lc[x];
        rls(x); return a < mr ? getColor(lcc) : getColor(rcc);
    }
 
    int getColor(int x){
        a = x;
        return getColor(rt);
    }
 
    int getCount(int x, int l, int r){
        if (b < l || r < a) return 0;
        if (a <= l && r <= b) return sc[x];
        rls(x); int z = getCount(lcc) + getCount(rcc);
        if (a <= ml && mr <= b && rc[lx] == lc[rx]) --z;
        return z;
    }
 
    int getCount(int _a, int _b){
        if (_a <= _b){
            a = _a, b = _b;
            return getCount(rt);
        }
        else{
            return getCount(_a,n-1) + getCount(0,_b) - (lc[1] == rc[1]);
        }
    }
 
    void Build(int x, int l, int r){
        if (l == r) sss(x, RD());
        else{
            s0[x] = 0; //!
            Build(lcc), Build(rcc);
            upd(x);
        }
    }
 
    void _Paint(int x, int l, int r){
        if (b < l || r < a) return;
        if (a <= l && r <= b) sss(x, c);
        else{
            rls(x);
            _Paint(lcc), _Paint(rcc);
            upd(x);
        }
    }
 
    void Paint(int _a, int _b, int _c){
 
        c = _c;
 
        if (_a <= _b){
            a = _a, b = _b, _Paint(rt);
        }
        else{
            a = _a, b = n-1, _Paint(rt);
            a = 0, b = _b, _Paint(rt);
        }
    }
 
 
    int offset; bool flip;
    void _R(int &x){if (x<0) x+=n; else if (x>=n) x-=n;}
    void _T(int &x){if (flip) x=n-x; x-=offset; _R(x);}
 
} using namespace T;
 
 
int main(){
 
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
 
    RD(n); RD(); Build(rt);
 
    char cmd[3]; int ca, cb, z, a, b; Rush{
        switch (RS(cmd)[0]){
            case 'R':
                if (!flip) offset += RD(); else offset -= RD();
                _R(offset);
                break;
            case 'F':
                flip = !flip;
                break;
            case 'S':
#define get_ab() RD(a,b);--a,--b;_T(a),_T(b); if (flip)swap(a,b)
                get_ab(); ca = getColor(a), cb = getColor(b);
                Paint(a,a,cb), Paint(b,b,ca);
                break;
            case 'P':
                get_ab(); RD(c);
                if (a<=b) Paint(a,b,c);
                else Paint(a,n-1,c), Paint(0,b,c);
                break;
            case 'C':
                if (cmd[1]=='S'){
                    get_ab();
                    z = getCount(a,b);
                }
                else{
                    z = sc[1]; if (z>1 && lc[1] == rc[1]) --z;
                }
                OT(z);
                break;
        }
    }
    return 0;
}

https://gist.github.com/lychees/61bc5dfa0c90ccd3901d

Posted by xiaodao
Category: BZOJ