题目
一个长为n(n<=5e5)的仅由'>"和'<'构成的字符串，
代表球桌上在1到n的位置，有n个转换器，
此外，球桌上还有0到n，共n+1个球洞，假设此时球碰到i位置的转换器，
对于i位置的<转换器，
①如果i=1，球会落到0位置球洞
②如果i-1位置是<转换器，球会滚到i-1的转换器
③如果i-1位置是>转换器，球会落到i-1位置球洞
对于i位置的>转换器，
①如果i=n，球会落到n位置球洞
②如果i+1位置是>转换器，球会滚到i+1的转换器
③如果i+1位置是<转换器，球会落到i位置球洞
以下q(q<=1e5)组询问，每次给出两个下标l,r，
首先，对[l,r]这段区间的符号取反(大于号变小于号，小于号变大于号)，取反操作保留到下一轮，
然后在[l,r]每个转换器上都放一个小球，要求输出，含最多小球的球洞中，小球的个数
本轮小球下落后即消失，不保留到下一轮
思路来源
Codeforces账户lucifer1004
https://codeforces.com/contest/1371/submission/85729867
题解
多种做法，但别的没太看懂，只好多打点标记，于是变成区间合并码农题，
如果出现><这样的情形，球会落在大于号的球洞里，
只考虑[l,r]时，如果区间左侧是<<或右侧>>，
说明会落在区间外的一个球洞里，因此答案是这三者的最大值
考虑维护分区间前缀、后缀、最大值来维护，
分别维护连续小于号、连续大于号、先一段小于号再一段大于号、先一段大于号再一段小于号
即，pl：前缀<<，pr：前缀>>，plr：前缀<<>>，prl：前缀>><<，
sl：后缀<<，sr：后缀>>，slr：后缀<<>>，srl：后缀>><<，
mxlr：区间最大<<>>，mxrl：区间最大>><<
考虑取反修改，完整区间就打取反标记，pushdown就将标记下放，pushup就将左子树和右子树merge
考虑回答，回答时，全在左就回答左，全在右就回答右，否则回答左右询问的merge
考虑pushup合并，pl、pr、sl、sr的合并是区间合并经典例题，区间最长01段的合并方法
pl：前缀<<，先等于左的前缀<<，如果等于左区间长，再加上右的前缀<<①
plr：前缀<>，先等于左的前缀<>，如果等于左区间长，再加上右的前缀>>①
另一种情况是，左的前缀<<等于左区间长，
若右的前缀>>非空，加上右的前缀>>②
若右的前缀<<>>非空，加上右的前缀<<>>③
注意到①、②、③三种情况互斥，故需要分别独立判断if
mxrl：最大区间><，用左mxrl、右mxrl，当前前缀prl，当前后缀srl分别更新一下，
然后考虑中间的两段，
若左子后缀>>非空且右子前缀<<非空，拼成>><<
无论左子后缀>>如何，若右子前缀>><<非空，拼成>><<
若左子后缀>><<非空，无论右子前缀<<如何，拼成>><<
以上若干情况，均可以考虑成，cin把cout向右推的一个过程，
此时，把>>和<<的临界点分为在左边、中间、右边三种情况考虑
代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,q,l,r;
char s[N];
struct node{
//p:前缀 s:后缀 l:小于号(朝左) r:大于号(朝右) mx:这一段最大值
int l,r,pl,pr,plr,prl,sl,sr,slr,srl,mxlr,mxrl;
bool tag;
void init(){
pl=pr=plr=prl=sl=sr=slr=srl=mxlr=mxrl=tag=0;
}
void out(){
printf("l:%d r:%d pl:%d pr:%d plr:%d prl:%d sl:%d sr:%d slr:%d srl:%d mxlr:%d mxrl:%d\n",l,r,pl,pr,plr,prl,sl,sr,slr,srl,mxlr,mxrl);
}
node(){
init();
}
}e[5*N];
node merge(node a,node b){
node c;
c.l=a.l;c.r=b.r;
c.pl=a.pl;if(a.pl==a.r-a.l+1)c.pl+=b.pl;//一种情况
c.pr=a.pr;if(a.pr==a.r-a.l+1)c.pr+=b.pr;
c.sl=b.sl;if(b.sl==b.r-b.l+1)c.sl+=a.sl;
c.sr=b.sr;if(b.sr==b.r-b.l+1)c.sr+=a.sr;
c.plr=a.plr;if(a.plr==a.r-a.l+1)c.plr+=b.pr;//三种情况
if(a.pl==a.r-a.l+1){
if(b.pr>0)c.plr=a.pl+b.pr;
if(b.plr>0)c.plr=a.pl+b.plr;
}
c.prl=a.prl;if(a.prl==a.r-a.l+1)c.prl+=b.pl;
if(a.pr==a.r-a.l+1){
if(b.pl>0)c.prl=a.pr+b.pl;
if(b.prl>0)c.prl=a.pr+b.prl;
}
c.slr=b.slr;if(b.slr==b.r-b.l+1)c.slr+=a.sl;
if(b.sr==b.r-b.l+1){
if(a.sl>0)c.slr=a.sl+b.sr;
if(a.slr>0)c.slr=a.slr+b.sr;
}
c.srl=b.srl;if(b.srl==b.r-b.l+1)c.srl+=a.sr;
if(b.sl==b.r-b.l+1){
if(a.sr>0)c.srl=a.sr+b.sl;
if(a.srl>0)c.srl=a.srl+b.sl;
}
c.mxlr=max(c.plr,c.slr);//七种情况
if(a.sl>0 && b.pr>0)c.mxlr=max(c.mxlr,a.sl+b.pr);
if(b.plr>0)c.mxlr=max(c.mxlr,a.sl+b.plr);
if(a.slr>0)c.mxlr=max(c.mxlr,a.slr+b.pr);
c.mxlr=max(c.mxlr,max(a.mxlr,b.mxlr));
c.mxrl=max(c.prl,c.srl);
if(a.sr>0 && b.pl>0)c.mxrl=max(c.mxrl,a.sr+b.pl);
if(b.prl>0)c.mxrl=max(c.mxrl,a.sr+b.prl);
if(a.srl>0)c.mxrl=max(c.mxrl,a.srl+b.pl);
c.mxrl=max(c.mxrl,max(a.mxrl,b.mxrl));
return c;
}
void bld(int p,int l,int r){
e[p].init();
e[p].l=l,e[p].r=r;
if(l==r){
if(s[l]=='<')e[p].pl=e[p].sl=1;
else e[p].pr=e[p].sr=1;
return;
}
int mid=(l+r)/2;
bld(p<<1,l,mid);bld(p<<1|1,mid+1,r);
e[p]=merge(e[p<<1],e[p<<1|1]);
}
void flip(int p){
swap(e[p].pl,e[p].pr),swap(e[p].sl,e[p].sr);
swap(e[p].plr,e[p].prl),swap(e[p].slr,e[p].srl),swap(e[p].mxlr,e[p].mxrl);
e[p].tag^=1;
}
void psd(int p){
if(e[p].tag){
flip(p<<1),flip(p<<1|1);
e[p].tag=0;
}
}
node ask(int p,int ql,int qr){//区间翻转+询问
if(e[p].l==ql&&e[p].r==qr){
flip(p);
return e[p];
}
psd(p);
int mid=(e[p].l+e[p].r)/2;
node ans;
if(qr<=mid)ans=ask(p<<1,ql,qr);
else if(ql>mid)ans=ask(p<<1|1,ql,qr);
else ans=merge(ask(p<<1,ql,mid),ask(p<<1|1,mid+1,qr));
e[p]=merge(e[p<<1],e[p<<1|1]);
return ans;
}
int main(){
scanf("%d%d",&n,&q);
scanf("%s",s+1);
bld(1,1,n);
while(q--){
scanf("%d%d",&l,&r);
node ans=ask(1,l,r);
printf("%d\n",max(ans.mxrl,max(ans.pl,ans.sr)));
}
return 0;
}
