前言
昨天晚上提交了 N 遍，甚至合并部分还改了一个写法，但是都在某个相同意义的一行显示 uninitialized value usage。
最后不知道改了什么，准备在洛谷提交一发然后走人，结果今天早上过来一看就 A 了？？？
细思极恐 2333。
\(\operatorname{Update:}\) 似乎有神仙还写动态 dp ？有空回来补一补。
题目
题目链接：https://codeforces.com/problemset/problem/1371/F
有 \(n\) 个连续的传送带，第 \(i\) 个传送带左右分别有编号为 \(i-1\) 和 \(i\) 的洞。每个传送带有一个传送方向。
假设第 \(i\) 个传送带是向前传送且上面有一个球，那么
- 如果第 \(i-1\) 个传送带是向后传送或者 \(i=1\)，那么球会掉落至第 \(i-1\) 个洞里。
- 如果第 \(i-1\) 个传送带是向前传送，那么球会到第 \(i-1\) 个传送带上。
向后传送同理。现在有若干询问，每次询问给出 \(l,r\)，意思是将 \([l,r]\) 的传送带反向。然后询问如果在 \([l,r]\) 的传送带内各放上一个球，那么最终球最多的洞中会有多少个球。
思路
首先可以把若干个 “>>><<” 看做一个块，也就是求会落到同一个洞里的区间看做一个块。
这道题一眼看过去就很线段树。我们考虑将 \([l,mid]\) 和 \((mid,r]\) 合并时，区间 \([l,r]\) 最多能放的球数 \(ans\) 就等于左右区间各自的 \(ans\) 以及 \([l,mid]\) 的最右一个块和 \((mid,r]\) 最左一个块产生的贡献的最大值。
所以我们在线段树的每一个节点上维护 \(llen,lpos,rlen,rpos\) 分别表示最左/右的块的长度以及求会落到哪一个洞内。
那么合并时，分别讨论四种情况，以合并最左的块为例：（| 表示 \(mid\) 的位置）
- 如果 \([l,mid].llen\) 等于其区间长度，那么需要考虑以下三种情况：
>>>|<<<，>>>|><<，><<|<<<。 - 否则 \([l,r]\) 最左的块就和 \([l,mid]\) 一样。
合并最右区间同理。具体细节请自行思考。反正也不是很难233
那么接下来就是区间修改操作了。我们发现直接修改不好在较优复杂度内重新维护那四个信息。但是在不修改其子区间的情况下，一个区间就只会有两种情况（正着和反着），所以我们可以在维护正着的四个信息时，同时维护如果把这个区间反过来的话的四个信息。维护其实是同理的，都是从子区间向上合并。
那如果修改区间 \([l,r]\)，那么就把该区间的正反的四个标记互换。然后给这个区间打上懒标记。下一次要其子区间信息时再向下维护。
对于区间询问，其实和合并时一个道理的。我直接暴力维护一个八元组 \((l,r,llen,lpos,rlen,rpos,ans,len)\)，然后将每一个子区间合并。
时间复杂度 \(O(n\log n)\)。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=500010;
int n,Q,ql,qr;
char ch[N];
struct Treenode
{
int l,r,lpos,rpos,llen,rlen,ans,len;
friend Treenode operator +(Treenode p,Treenode q)
{
Treenode x;
int mid=p.r;
x.l=p.l; x.r=q.r;
if (p.llen==p.len && p.lpos>=mid && q.lpos<=mid)
x.lpos=mid,x.llen=p.llen+q.llen;
else if (p.llen==p.len && p.lpos>=mid && q.lpos>mid)
x.lpos=q.lpos,x.llen=p.llen+q.llen;
else if (p.llen==p.len && p.lpos<mid && q.lpos<=mid)
x.lpos=p.lpos,x.llen=p.llen+q.llen;
else
x.lpos=p.lpos,x.llen=p.llen;
if (q.rlen==q.len && p.rpos>=mid && q.rpos<=mid)
x.rpos=mid,x.rlen=p.rlen+q.rlen;
else if (q.rlen==q.len && p.rpos>=mid && q.rpos>mid)
x.rpos=q.rpos,x.rlen=p.rlen+q.rlen;
else if (q.rlen==q.len && p.rpos<mid && q.rpos<=mid)
x.rpos=p.rpos,x.rlen=p.rlen+q.rlen;
else
x.rpos=q.rpos,x.rlen=q.rlen;
x.ans=max(p.ans,q.ans);
if (p.rpos>=mid || q.lpos<=mid) x.ans=max(x.ans,p.rlen+q.llen);
return x;
}
};
struct SegTree
{
int l[N*4],r[N*4],lpos[2][N*4],rpos[2][N*4],llen[2][N*4],rlen[2][N*4],ans[2][N*4],len[N*4],lazy[N*4];
void rev(int x)
{
lazy[x]^=1;
swap(llen[0][x],llen[1][x]); swap(lpos[0][x],lpos[1][x]);
swap(rlen[0][x],rlen[1][x]); swap(rpos[0][x],rpos[1][x]);
swap(ans[0][x],ans[1][x]);
}
void pushup(int x)
{
int mid=(l[x]+r[x])>>1;
for (int id=0;id<=1;id++)
{
if (llen[id][x*2]==len[x*2] && lpos[id][x*2]>=mid && lpos[id][x*2+1]<=mid)
lpos[id][x]=mid,llen[id][x]=llen[id][x*2]+llen[id][x*2+1];
else if (llen[id][x*2]==len[x*2] && lpos[id][x*2]>=mid && lpos[id][x*2+1]>mid)
lpos[id][x]=lpos[id][x*2+1],llen[id][x]=llen[id][x*2]+llen[id][x*2+1];
else if (llen[id][x*2]==len[x*2] && lpos[id][x*2]<mid && lpos[id][x*2+1]<=mid)
lpos[id][x]=lpos[id][x*2],llen[id][x]=llen[id][x*2]+llen[id][x*2+1];
else
lpos[id][x]=lpos[id][x*2],llen[id][x]=llen[id][x*2];
if (rlen[id][x*2+1]==len[x*2+1] && rpos[id][x*2]>=mid && rpos[id][x*2+1]<=mid)
rpos[id][x]=mid,rlen[id][x]=rlen[id][x*2]+rlen[id][x*2+1];
else if (rlen[id][x*2+1]==len[x*2+1] && rpos[id][x*2]>=mid && rpos[id][x*2+1]>mid)
rpos[id][x]=rpos[id][x*2+1],rlen[id][x]=rlen[id][x*2]+rlen[id][x*2+1];
else if (rlen[id][x*2+1]==len[x*2+1] && rpos[id][x*2]<mid && rpos[id][x*2+1]<=mid)
rpos[id][x]=rpos[id][x*2],rlen[id][x]=rlen[id][x*2]+rlen[id][x*2+1];
else
rpos[id][x]=rpos[id][x*2+1],rlen[id][x]=rlen[id][x*2+1];
ans[id][x]=max(ans[id][x*2],ans[id][x*2+1]);
if (rpos[id][x*2]>=mid) ans[id][x]=max(ans[id][x],rlen[id][x*2]+llen[id][x*2+1]);
if (lpos[id][x*2+1]<=mid) ans[id][x]=max(ans[id][x],rlen[id][x*2]+llen[id][x*2+1]);
}
}
void pushdown(int x)
{
if (lazy[x])
{
lazy[x]=0;
rev(x*2); rev(x*2+1);
}
}
void build(int x,int ql,int qr)
{
l[x]=ql; r[x]=qr; len[x]=qr-ql+1;
if (ql==qr)
{
ans[0][x]=llen[0][x]=rlen[0][x]=ans[1][x]=llen[1][x]=rlen[1][x]=1;
if (ch[ql]=='<') lpos[0][x]=rpos[0][x]=ql-1,lpos[1][x]=rpos[1][x]=qr;
if (ch[ql]=='>') lpos[0][x]=rpos[0][x]=qr,lpos[1][x]=rpos[1][x]=ql-1;
return;
}
int mid=(ql+qr)>>1;
build(x*2,ql,mid); build(x*2+1,mid+1,qr);
pushup(x);
}
void update(int x,int ql,int qr)
{
if (l[x]==ql && r[x]==qr)
{
rev(x);
return;
}
pushdown(x);
int mid=(l[x]+r[x])>>1;
if (qr<=mid) update(x*2,ql,qr);
else if (ql>mid) update(x*2+1,ql,qr);
else update(x*2,ql,mid),update(x*2+1,mid+1,qr);
pushup(x);
}
Treenode query(int x,int ql,int qr)
{
if (l[x]==ql && r[x]==qr)
return (Treenode){l[x],r[x],lpos[0][x],rpos[0][x],llen[0][x],rlen[0][x],ans[0][x],len[x]};
pushdown(x);
int mid=(l[x]+r[x])>>1;
if (qr<=mid) return query(x*2,ql,qr);
if (ql>mid) return query(x*2+1,ql,qr);
return query(x*2,ql,mid)+query(x*2+1,mid+1,qr);
}
}seg;
int main()
{
scanf("%d%d",&n,&Q);
scanf("%s",ch+1);
seg.build(1,1,n);
while (Q--)
{
scanf("%d%d",&ql,&qr);
seg.update(1,ql,qr);
printf("%d\n",seg.query(1,ql,qr).ans);
}
return 0;
}