注意分类讨论完整性：CF1371F

https://www.luogu.com.cn/problem/CF1371F

此题要分类讨论完全

容易漏掉 >>>>><<<<< 在左右或中间的情况

多对拍

#include
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 500010
//#define M
//#define mo
int n, m, i, j, k, T;
int l, r, q, rt; 
char str[N]; 

struct Segment_tree {
	int tot, ls[N<<2], rs[N<<2], tag[N<<2]; 
	struct node {
		int s, L, R, mx, Lx, Rx; 
	}s[N<<2][2]; 
	node merge(node a, node b) {
		node c; c.s=a.s+b.s; 
		if(a.L==a.s) c.L=a.s+b.L; else c.L=a.L; 
		if(b.R==b.s) c.R=b.s+a.R; else c.R=b.R; 
		c.mx=max(a.mx, b.mx); 
		c.mx=max(c.mx, max(c.L, c.R)); 
		c.mx=max(c.mx, a.R+b.L); 
		if(a.Lx==a.s) c.Lx=a.s+b.L; else c.Lx=a.Lx; 
		if(b.Rx==b.s) c.Rx=b.s+a.R; else c.Rx=b.Rx; 
		if(a.R==a.s) c.Lx=max(c.Lx, a.s+b.Lx); 
		if(b.L==b.s) c.Rx=max(c.Rx, b.s+a.Rx); 
		c.mx=max(c.mx, max(c.Lx, c.Rx)); 
		c.mx=max(c.mx, a.R+b.Lx); 
		c.mx=max(c.mx, b.L+a.Rx); 
		return c; 
	}
	void push_up(int k) {
		s[k][0]=merge(s[ls[k]][0], s[rs[k]][0]); 
		s[k][1]=merge(s[ls[k]][1], s[rs[k]][1]); 
	}
	void build(int &k, int l, int r) {
		if(!k) k=++tot; 
		if(l==r) {
			if(str[l]=='<') s[k][0].L=1, s[k][1].R=1; 
			else s[k][0].R=1, s[k][1].L=1; 
			s[k][0].s=s[k][1].s=s[k][0].mx=s[k][1].mx=1; 
			s[k][0].Lx=s[k][0].Rx=s[k][1].Lx=s[k][1].Rx=1; 
			return ; 
		}
		int mid=(l+r)>>1; 
		build(ls[k], l, mid); 
		build(rs[k], mid+1, r); 
		push_up(k); 
	}
	void fan(int k) {
		tag[k]^=1; swap(s[k][0], s[k][1]); 
	}
	void push_down(int k) {
		if(!tag[k]) return ; 
		fan(ls[k]); fan(rs[k]); 
		tag[k]=0; 
	}
	void print(node a) {
		printf("%d %d | %d %d | %d %d\n", a.mx, a.s, a.L, a.R, a.Lx, a.Rx); 
	}
	node modify(int k, int l, int r, int x, int y) {
//		printf("%d [%d %d]\n", k, l, r); 
		if(l>=x && r<=y) return fan(k), s[k][0]; 
		int mid=(l+r)>>1, flg=0; push_down(k); 
		node a, b, c; 
		if(x<=mid) a=modify(ls[k], l, mid, x, y), flg|=1; 
		if(y>=mid+1) b=modify(rs[k], mid+1, r, x, y), flg|=2; 
		push_up(k); 
		if(flg==1) return a; if(flg==2) return b; 
		c=merge(a, b); 
//		printf("%d : %d %d | %d %d | %d %d\n", k, c.mx, c.s, c.L, c.R, c.Lx, c.Rx); 
//		print(a); print(b); 
//		printf("%d : %d %d | %d %d | %d %d\n", k, a.mx, c.s, c.L, c.R, c.Lx, c.Rx); 
		return merge(a, b); 
	}
}Seg;

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}
	n=read(); q=read(); 
	scanf("%s", str+1); 
	Seg.build(rt, 1, n); 
	while(q--) {
		l=read(); r=read(); 
		printf("%d\n", Seg.modify(1, 1, n, l, r).mx); 
	}
	return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104