你说得对,但是我 15k 分讨改出来了!
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch = getchar();lx x = 0 , f = 1;
for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;
for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);
return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int , int>
#define fi first
#define se second
const int Ratio = 0;
const int N = 2e5 + 5, x = 1e9;
const int mod = 1e9 + 7;
int n, m;
string s;
int a[N];
struct rmm
{
int llx, rlx, wlx;
int ln, rn;
bool wudi;
rmm(){llx = rlx = wlx = ln = rn = 0; wudi = 0;}
} t[N << 2];
namespace Wisadel
{
int W(char c)
{
if(c == 'R') return 1;
else if(c == 'S') return 2;
else return 3;
}
char M(int x)
{
if(x == 1) return 'R';
else if(x == 2) return 'S';
else return 'P';
}
int Wpk(int aa, int bb)
{
if(!aa || !bb) return aa + bb;
if(aa == bb) return aa;
if(((aa == 1 || aa == 2) && bb == aa + 1) || (aa == 3 && bb == 1) ) return aa;
return bb;
}
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define mid ((l + r) >> 1)
rmm Wpushup(rmm a, rmm b)
{
rmm c;
c.llx = a.llx, c.rlx = b.rlx;
c.ln = c.rn = 0;
c.wudi = 0;
int wn = Wpk(a.rlx, b.llx);
if(a.wudi && b.wudi)
{
if(a.rlx != b.llx)
{
if(wn == a.rlx)//
{
if(a.ln + 1 > b.rn)
{
c.wlx = a.wlx;
c.rn = a.rn, c.ln = a.ln + 1 - b.rn + b.ln;
}
else
{
c.wlx = b.wlx;
c.ln = b.ln, c.rn = b.rn - 1 - a.ln + a.rn;
}
}
else
{
if(a.ln > b.rn + 1)
{
c.wlx = a.wlx;
c.rn = a.rn, c.ln = a.ln - 1 - b.rn + b.ln;
}
else
{
c.wlx = b.wlx;
c.ln = b.ln, c.rn = b.rn + 1 - a.ln + a.rn;
}
}
}
else
{
if(a.ln > b.rn)
{
c.wlx = a.wlx;
c.rn = a.rn, c.ln = a.ln - b.rn + b.ln;
}
else
{
c.wlx = b.wlx;
c.ln = b.ln, c.rn = b.rn - a.ln + a.rn;
}
}
c.wudi = 1;
return c;
}
if(a.wudi)
{
if(a.rlx != b.llx)
{
if(wn == a.rlx)
{
if(b.ln)
{
c.wlx = a.wlx;
c.rn = a.rn, c.ln = a.ln + b.ln + 1;
c.wudi = 1;
}
else if(b.rn)
{
if(a.ln + 1 > b.rn)
{
c.wlx = a.wlx;
c.rn = a.rn, c.ln = a.ln + 1 - b.rn;
c.wudi = 1;
}
else
{
c.wlx = b.wlx;
c.rn = b.rn - a.ln - 1 + a.rn;
}
}
else
{
c.wlx = a.wlx;
c.rn = a.rn, c.ln = a.ln + 1;
c.wudi = 1;
}
}
else
{
if(b.ln)
{
c.wlx = a.wlx;
c.rn = a.rn, c.ln = a.ln + b.ln - 1;
c.wudi = 1;
}
else if(b.rn)
{
if(a.ln - 1 > b.rn)
{
c.wlx = a.wlx;
c.rn = a.rn, c.ln = a.ln - 1 - b.rn;
c.wudi = 1;
}
else
{
c.wlx = b.wlx;
c.rn = b.rn - a.ln + 1 + a.rn;
}
}
else
{
c.wlx = a.wlx;
c.rn = a.rn;
if(a.ln > 1)
{
c.ln = a.ln - 1;
c.wudi = 1;
}
}
}
}
else
{
if(b.ln)
{
c.wlx = a.wlx;
c.rn = a.rn, c.ln = a.ln + b.ln;
c.wudi = 1;
}
else if(b.rn)
{
if(a.ln > b.rn)
{
c.wlx = a.wlx;
c.rn = a.rn, c.ln = a.ln - b.rn;
c.wudi = 1;
}
else
{
c.wlx = b.wlx;
c.rn = b.rn - a.ln + a.rn;
}
}
else
{
c.wlx = a.wlx;
c.ln = a.ln, c.rn = a.rn;
c.wudi = 1;
}
}
return c;
}
if(b.wudi)
{
if(a.rlx != b.llx)
{
if(wn == b.llx)
{
if(a.rn)
{
c.wlx = b.wlx;
c.ln = b.ln, c.rn = b.rn + 1 + a.rn;
c.wudi = 1;
}
else if(a.ln)
{
if(b.rn + 1 > a.ln)
{
c.wlx = b.wlx;
c.ln = b.ln, c.rn = b.rn + 1 - a.ln;
c.wudi = 1;
}
else
{
c.wlx = a.wlx;
c.ln = a.ln - 1 - b.rn + b.ln;
}
}
else
{
c.wlx = b.wlx;
c.ln = b.ln, c.rn = b.rn + 1;
c.wudi = 1;
}
}
else
{
if(a.rn)
{
c.wlx = b.wlx;
c.ln = b.ln, c.rn = b.rn - 1 + a.rn;
c.wudi = 1;
}
else if(a.ln)
{
if(b.rn - 1 > a.ln)
{
c.wlx = b.wlx;
c.ln = b.ln, c.rn = b.rn - 1 - a.ln;
c.wudi = 1;
}
else
{
c.wlx = a.wlx;
c.ln = a.ln + 1 - b.rn + b.ln;
}
}
else
{
c.wlx = b.wlx;
c.ln = b.ln;
if(b.rn > 1)
{
c.rn = b.rn - 1;
c.wudi = 1;
}
}
}
}
else
{
if(a.rn)
{
c.wlx = b.wlx;
c.ln = b.ln, c.rn = b.rn + a.rn;
c.wudi = 1;
}
else if(a.ln)
{
if(b.rn > a.ln)
{
c.wlx = b.wlx;
c.ln = b.ln, c.rn = b.rn - a.ln;
c.wudi = 1;
}
else
{
c.wlx = a.wlx;
c.ln = a.ln - b.rn + b.ln;
}
}
else
{
c.wlx = b.wlx;
c.ln = b.ln, c.rn = b.rn;
c.wudi = 1;
}
}
return c;
}
//
if(a.rlx != b.llx)
{
if(wn == a.rlx)//
{
if((a.ln && b.ln) || (!a.ln && !a.rn && b.ln) || (a.ln && !b.ln && !b.rn))
{
c.wlx = a.wlx;
c.ln = a.ln + b.ln + 1;
}
else if(a.ln && b.rn)
{
if(a.ln > b.rn - 1)
{
c.wlx = a.wlx;
c.ln = a.ln - b.rn + 1;
}
else
{
c.wlx = b.wlx;
c.rn = b.rn - 1 - a.ln;
}
}
else if((a.rn && b.ln) || (a.rn && !b.ln && !b.rn))
{
c.wlx = a.wlx;
c.ln = b.ln + 1;
c.rn = a.rn;
c.wudi = 1;
}
else if(a.rn && b.rn)
{
c.wlx = b.wlx;
c.rn = a.rn + b.rn - 1;
}
else if(!a.ln && !a.rn && !b.ln && !b.rn)
{
c.wlx = a.wlx;
c.ln = 1;
}
else if(!a.ln && !a.rn && b.rn)
{
c.wlx = b.wlx;
c.rn = b.rn - 1;
}
}
if(wn == b.llx)// ←
{
// cout<<"BUOK!"<<endl;
if((a.rn && b.rn) || (!a.ln && !a.rn && b.rn) || (a.rn && !b.ln && !b.rn))
{
c.wlx = b.wlx;
c.rn = a.rn + b.rn + 1;
}
else if(a.ln && b.rn)
{
if(b.rn > a.ln - 1)
{
c.wlx = b.wlx;
c.rn = b.rn - a.ln + 1;
}
else
{
c.wlx = a.wlx;
c.ln = a.ln - 1 - b.rn;
}
}
else if((a.rn && b.ln) || (b.ln && !a.ln && !a.rn))
{
c.wlx = b.wlx;
c.ln = b.ln;
c.rn = a.rn + 1;
c.wudi = 1;
}
else if(a.ln && b.ln)
{
c.wlx = a.wlx;
c.ln = a.ln + b.ln - 1;
}
else if(!a.ln && !a.rn && !b.ln && !b.rn)
{
c.wlx = b.wlx;
c.rn = 1;
}
else if(a.ln && !b.ln && !b.rn)
{
// cout<<"BUOK!"<<endl;
c.wlx = a.wlx;
c.ln = a.ln - 1;
}
}
}
else
{
if((a.ln && b.ln) || (!a.ln && !a.rn && b.ln) || (a.ln && !b.ln && !b.rn))
{
c.wlx = a.wlx;
c.ln = a.ln + b.ln;
}
else if((a.ln && b.rn))
{
if(a.ln > b.rn)
{
c.wlx = a.wlx;
c.ln = a.ln - b.rn;
}
else
{
c.wlx = b.wlx;
c.rn = b.rn - a.ln;
}
}
else if(a.rn && b.ln)
{
c.wlx = a.wlx;
c.rn = a.rn, c.ln = b.ln;
c.wudi = 1;
}
else if((a.rn && b.rn) || (!a.ln && !a.rn && b.rn) || (a.rn && !b.ln && !b.rn))
{
c.wlx = b.wlx;
c.rn = a.rn + b.rn;
}
else if(!a.ln && !a.rn && !b.ln && !b.rn)
{
c.wlx = a.wlx;
}
}
return c;
}
void Wbuild(int rt, int l, int r)
{
if(l == r)
{
t[rt].llx = t[rt].rlx = t[rt].wlx = a[l];
t[rt].ln = t[rt].rn = 0;
return;
}
Wbuild(ls, l, mid), Wbuild(rs, mid + 1, r);
t[rt] = Wpushup(t[ls], t[rs]);
// cout<<l<<' '<<r<<' '<<t[rt].ln<<' '<<t[rt].rn<<' '<<t[rt].wlx<<' '<<t[rt].wudi<<endl;
}
void Wupd(int rt, int l, int r, int x, int k)
{
if(l == r)
{
t[rt].llx = t[rt].rlx = t[rt].wlx = k;
t[rt].ln = t[rt].rn = 0;
return;
}
if(x <= mid) Wupd(ls, l, mid, x, k);
else Wupd(rs, mid + 1, r, x, k);
t[rt] = Wpushup(t[ls], t[rs]);
}
rmm Wq(int rt, int l, int r, int x, int y)
{
if(x <= l && r <= y) return t[rt];
rmm lans, rans; int ly = 0, ry = 0;
if(x <= mid) lans = Wq(ls, l, mid, x, y), ly = 1;
if(y > mid) rans = Wq(rs, mid + 1, r, x, y), ry = 1;
if(ly && ry)
{
// cout<<l<<' '<<mid<<' '<<r<<endl;
// cout<<lans.ln<<' '<<lans.rn<<' '<<lans.wlx<<' '<<lans.wudi<<endl;
// cout<<rans.ln<<' '<<rans.rn<<' '<<rans.wlx<<' '<<rans.wudi<<endl;
// cout<<endl;
return Wpushup(lans, rans);
}
else if(ly) return lans;
else return rans;
}
short main()
{
// freopen(".in", "r", stdin) , freopen(".out", "w", stdout);
freopen("a.in", "r", stdin) , freopen("a.out", "w", stdout);
n = qr, m = qr;
cin>>s;
fo(i, 0, n - 1) a[i + 1] = W(s[i]);
Wbuild(1, 1, n);
fo(i, 1, m)
{
int op = qr, l = qr, r; char ch;
if(op == 1)
{
scanf(" %c", &ch);
Wupd(1, 1, n, l, W(ch));
}
else
{
r = qr;
// fo(j, l, r)
// {
// cout<<M(Wq(1, 1, n, j, j).wlx);
// }
// cout<<endl;
rmm zc = Wq(1, 1, n, l, r);
// cout<<zc.ln<<' '<<zc.rn<<' '<<zc.llx<<' '<<zc.rlx<<' ';
printf("%c\n", M(zc.wlx));
}
}
return Ratio;
}
}
int main(){return Wisadel::main();}
标签:wlx,ln,T3,else,wudi,&&,rn
From: https://www.cnblogs.com/Ratio-Yinyue1007/p/18446872