2020-2021:teams:wangzai_milk:codeforces_round_654_div._2_zars19

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:wangzai_milk:codeforces_round_654_div._2_zars19 [2020/07/17 22:02]
zars19
+++ 2020-2021:teams:wangzai_milk:codeforces_round_654_div._2_zars19 [2020/07/18 01:30] (当前版本)
zars19
@@ 行 173: / 行 173: @@
 	for(int i=st;i<res;i++)printf("%d ",i);
 	puts("");
+	return 0;
+}
+</code></hidden>
+\\
+====== F. Raging Thunder ======
+认真读题之后发现其实是给出一个左右串，每次反转（左变右右变左）一个区间查询> > > < < < < <形状最长长度。
+很明显线段树+lazy tag，维护> > < <形状最长长度、< < < > >形状最长长度、左右两边的两种形状长度、左右两边<和>的长度。
+<hidden><code cpp>
+#include<bits/stdc++.h>
+#define ll long long
+using namespace std;
+const int N=5e5+10;
+char s[N];
+struct Node
+{
+	int lR,lL,rL,rR,maxn,tmaxn,lz,sz,lmaxn,rmaxn,ltmaxn,rtmaxn;
+}t[N*4];
+Node combine(Node a,Node b)
+{
+	Node x;
+	x.lR=a.lR;
+	if(x.lR==a.sz)x.lR+=b.lR;
+	x.lL=a.lL;
+	if(x.lL==a.sz)x.lL+=b.lL;
+	x.rR=b.rR;
+	if(x.rR==b.sz)x.rR+=a.rR;
+	x.rL=b.rL;
+	if(x.rL==b.sz)x.rL+=a.rL;
+	x.maxn=max(max(a.maxn,b.maxn),max(a.rmaxn+b.lL,a.rR+b.lmaxn));
+	x.tmaxn=max(max(a.tmaxn,b.tmaxn),max(a.rtmaxn+b.lR,a.rL+b.ltmaxn));
+	x.lmaxn=a.lmaxn;
+	if(x.lmaxn==a.sz)x.lmaxn+=b.lL;
+	if(a.lR==a.sz)x.lmaxn=max(x.lmaxn,a.sz+b.lmaxn);
+	x.ltmaxn=a.ltmaxn;
+	if(x.ltmaxn==a.sz)x.ltmaxn+=b.lR;
+	if(a.lL==a.sz)x.ltmaxn=max(x.ltmaxn,a.sz+b.ltmaxn);
+	x.rmaxn=b.rmaxn;
+	if(x.rmaxn==b.sz)x.rmaxn+=a.rR;
+	if(b.rL==b.sz)x.rmaxn=max(x.rmaxn,b.sz+a.rmaxn);
+	x.rtmaxn=b.rtmaxn;
+	if(x.rtmaxn==b.sz)x.rtmaxn+=a.rL;
+	if(b.rR==b.sz)x.rtmaxn=max(x.rtmaxn,b.sz+a.rtmaxn);
+	x.sz=a.sz+b.sz,x.lz=0;
+	return x;
+}
+void build(int idx,int l,int r)
+{
+	if(l==r)
+	{
+		t[idx].rR=t[idx].lR=(s[l]=='>');
+		t[idx].rL=t[idx].lL=(s[l]=='<');
+		t[idx].maxn=t[idx].tmaxn=t[idx].lmaxn=t[idx].rmaxn=t[idx].ltmaxn=t[idx].rtmaxn=1;
+		t[idx].sz=1,t[idx].lz=0;
+		return;
+	}
+	int mid=(l+r)>>1;
+	build(idx<<1,l,mid),build(idx<<1|1,mid+1,r);
+	t[idx]=combine(t[idx<<1],t[idx<<1|1]);
+}
+void rev(int idx)
+{
+	t[idx].lz^=1;
+	swap(t[idx].lL,t[idx].lR),swap(t[idx].rR,t[idx].rL),swap(t[idx].maxn,t[idx].tmaxn);
+	swap(t[idx].lmaxn,t[idx].ltmaxn),swap(t[idx].rmaxn,t[idx].rtmaxn);
+}
+void pushdown(int idx)
+{
+	if(!t[idx].lz)return;
+	t[idx].lz=0,rev(idx<<1),rev(idx<<1|1);
+}
+void change(int idx,int l,int r,int a,int b)
+{
+	if(a<=l&&b>=r){rev(idx);return;}
+	pushdown(idx);
+	int mid=(l+r)>>1;
+	if(b<=mid)change(idx<<1,l,mid,a,b);
+	else if(a>mid)change(idx<<1|1,mid+1,r,a,b);
+	else change(idx<<1,l,mid,a,b),change(idx<<1|1,mid+1,r,a,b);
+	t[idx]=combine(t[idx<<1],t[idx<<1|1]);
+}
+Node query(int idx,int l,int r,int a,int b)
+{
+	if(a<=l&&b>=r)return t[idx];
+	pushdown(idx);
+	int mid=(l+r)>>1;
+	if(b<=mid)return query(idx<<1,l,mid,a,b);
+	else if(a>mid)return query(idx<<1|1,mid+1,r,a,b);
+	else return combine(query(idx<<1,l,mid,a,b),query(idx<<1|1,mid+1,r,a,b));
+}
+int main()
+{
+	int n,q;
+	scanf("%d%d%s",&n,&q,s+1);
+	build(1,1,n);
+	for(int i=1;i<=q;i++)
+	{
+		int l,r;
+		scanf("%d%d",&l,&r);
+		change(1,1,n,l,r);
+		printf("%d\n",query(1,1,n,l,r).maxn);
+	}
 	return 0;
 }
 </code></hidden>
 \\

2020-2021/teams/wangzai_milk/codeforces_round_654_div._2_zars19.1594994567.txt.gz · 最后更改: 2020/07/17 22:02 由 zars19