钦州的网站建设,公司网站购物平台建设,ip域名解析查询,浏览器在线打开网页正题
题目链接:https://www.luogu.org/problemnew/show/P4130 题目大意
一个环形颜色珠子链#xff0c;位置(注意不是上面的珠子)从最上顺时针下来位置依次标号1∼n1\sim n1∼n。 然后要求支持以下操作 Rk:R\ k:R k:将所有珠子顺时针旋转kkk个。F:F:F:将所有珠子以111向下翻…正题
题目链接:https://www.luogu.org/problemnew/show/P4130 题目大意
一个环形颜色珠子链位置(注意不是上面的珠子)从最上顺时针下来位置依次标号1∼n1\sim n1∼n。 然后要求支持以下操作
Rk:R\ k:R k:将所有珠子顺时针旋转kkk个。F:F:F:将所有珠子以111向下翻转Sij:S\ i\ j:S i j:交换iii和jjj上的珠子Pijk:P\ i\ j\ k:P i j k:将iii顺时针到jjj的珠子都涂上颜色kkkC:C:C:询问整个链有多少颜色段CSij:CS\ i\ j:CS i j:询问iii顺时针到jjj有多少颜色段。
(颜色段为连续的相同颜色) 解题思路
先不考虑前两个操作我们可以用线段树进行操作。
储存[l,r,w,lc,rc,lazy][l,r,w,lc,rc,lazy][l,r,w,lc,rc,lazy]分别表示下标l∼rl\sim rl∼r有www个颜色段头颜色为lclclc尾颜色为rcrcrc懒惰标签lazylazylazy
然后我们可以利用lc,rclc,rclc,rc进行合并。
之后我们就可以轻易的实现后4个操作。
那我们考虑前两个操作我们会发现它并不会破坏连续性也就是任何一个位置相邻的两个位置的数字编号也与其相邻。
那么我们就可以使用一个十分优秀的算法我们用ttt记录其旋转了几步然后用BBB记录是否翻转(因为翻转两次等于没有翻转)。之后就可以计算出给出的数字段旋转和翻转之前应该在哪个位置。 然后照样计算就好了。 codecodecode
#includecstdio
#includealgorithm
#includecstring
using namespace std;
const int N500100;
struct Tree_node{int l,r,w,lc,rc,lazy;
}ans;
int n,C,m,t,B;
struct Line_cut_tree{Tree_node t[N2];
// node merge(node tl,node tr)
// {
// node t;
// t.wtl.wtr.w(tl.rc!tr.lc);
// return t;
// }void megre(Tree_node t,Tree_node tl,Tree_node tr){t.lctl.lc;t.rctr.rc;t.wtl.wtr.w-(tl.rctr.lc);}void build(int x,int l,int r){t[x].ll;t[x].rr;if(lr){scanf(%d,t[x].lc); t[x].rct[x].lc;t[x].w1;return;}int mid(lr)/2;build(x*2,l,mid);build(x*21,mid1,r);megre(t[x],t[x*2],t[x*21]);}void downdata(int x){if(!t[x].lazy) return;t[x*2].lazyt[x*21].lazyt[x].lazy;t[x*2].wt[x*21].w1;t[x*2].lct[x*2].rct[x*21].lct[x*21].rct[x].lazy;t[x].lazy0;}void Ask(int x,int l,int r){if(t[x].llt[x].rr){if(!ans.rc) ans.lct[x].lc;megre(ans,ans,t[x]);return;}downdata(x);if(rt[x*2].r) Ask(x*2,l,r);else if(lt[x*2].r) Ask(x*21,l,r);else Ask(x*2,l,t[x*2].r),Ask(x*21,t[x*21].l,r);megre(t[x],t[x*2],t[x*21]);}void Change(int x,int l,int r,int z){if(t[x].llt[x].rr){t[x].w1;t[x].lazyt[x].rct[x].lcz;return;}downdata(x);if(rt[x*2].r) Change(x*2,l,r,z);else if(lt[x*2].r) Change(x*21,l,r,z);else Change(x*2,l,t[x*2].r,z),Change(x*21,t[x*21].l,r,z);megre(t[x],t[x*2],t[x*21]);}
}Tree;
void Reset()
{ans.wans.rc0;}
void doing(int x,int y)
{if(!B){if(xt1) xx-t;else xn-tx;if(yt1) yy-t;else yn-ty;}else{if(xt1) xt-x2;else xtn-x2;if(yt1) yt-y2;else ytn-y2;swap(x,y);}
}
int main()
{scanf(%d%d,n,C);Tree.build(1,1,n);scanf(%d,m);for(int i1;im;i){char op[3];scanf(%s,op);if(op[0]C){if(op[1]S){int x,y;scanf(%d%d,x,y);if(xy)x,x--;doing(x,y);if(yx) Reset(),Tree.Ask(1,x,y);else {Tree_node a1,a2;Reset();Tree.Ask(1,x,n);a1ans;Reset();Tree.Ask(1,1,y);a2ans;if(B){swap(a1.lc,a1.rc);swap(a2.lc,a2.rc);swap(a1,a2);}Tree.megre(ans,a1,a2);}printf(%d\n,ans.w);}elseprintf(%d\n,max(Tree.t[1].w-(Tree.t[1].lcTree.t[1].rc),1));}else if(op[0]R){int k;scanf(%d,k);t(tk)%n;}else if(op[0]F) B^1,tn-t;else if(op[0]S){int x,y;scanf(%d%d,x,y);doing(x,y);Reset();Tree.Ask(1,x,x);int a1ans.lc;Reset();Tree.Ask(1,y,y);int a2ans.lc;Tree.Change(1,x,x,a2);Tree.Change(1,y,y,a1);}else if(op[0]P){int x,y,z;scanf(%d%d%d,x,y,z);doing(x,y);if(yx) Tree.Change(1,x,y,z);else Tree.Change(1,x,n,z),Tree.Change(1,1,y,z);}}
}
