# 某岛

… : "…アッカリ～ン . .. . " .. .
September 27, 2014

# BZOJ 1493. [NOI2007]项链工厂

### 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