\u5f00\u4e00\u9897\u73c2\u6735\u8389\u6811\uff0c\u5bf9\u4e8e\u6bcf\u4e2a\u65b0\u7684\u67e5\u8be2\uff0c\u5148\u628al-1,l\u4e4b\u95f4\u548cr,r+1\u4e4b\u95f4split\u5f00\uff0c\u7136\u540e\u5bf9\u4e8e\u5269\u4e0b\u7684\u90e8\u4efd\u7528\u6876\u6392\u5e8f\u5e76\u66b4\u529b\u5408\u5e76\u5373\u53ef\u3002<\/p>\n\n\n\n
#include<iostream>\r\n#include<cstdio>\r\n#include<cstring>\r\n#include<algorithm>\r\n#include<queue>\r\n#include<vector>\r\n#include<set> \r\nusing namespace std;\r\nconst int N=100005;\r\n\r\nstruct Data{\r\n\tint l;int r;char id;\r\n\tbool operator<(const Data &B)const{\r\n\t\treturn r<B.r;\r\n\t}\r\n};\r\nint n,q;\r\nchar ch[N];\r\nstd::set<Data> st;\r\ninline void split(std::set<Data>::iterator it, int X){\r\n\tint l=it->l,r=it->r;char id=it->id;\r\n\tif(X<l||X>=r){\r\n\t\treturn;\r\n\t}\r\n\tst.erase(it);st.insert((Data){l,X,id});st.insert((Data){X+1,r,id});\r\n}\r\nint bckt[30];\r\ninline void clr(){\r\n\tfor(int i=0;i<26;++i){\r\n\t\tbckt[i]=0;\r\n\t}\r\n}\r\ninline void uni(int l,int r,int op){\r\n\tstd::set<Data>::iterator itx,ity;\r\n\titx=st.lower_bound((Data){0,l-1,0});\r\n\tsplit(itx,l-1);\r\n\tity=st.lower_bound((Data){0,r,0});\r\n\tsplit(ity,r);\r\n\titx=st.lower_bound((Data){0,l,0});\r\n\tity=st.lower_bound((Data){0,r,0});\r\n\t++ity;\r\n\tfor(std::set<Data>::iterator it=itx;it!=ity;++it){\r\n\t\tbckt[(it->id)-'a']+=(it->r)-(it->l)+1;\r\n\t}\r\n\tst.erase(itx,ity);\r\n\tint loc,nl=l;\r\n\tfor(int i=0;i<26;++i){\r\n\t\tloc=op?i:(26-i-1);\r\n\t\tif(bckt[loc]<=0){\r\n\t\t\tcontinue;\r\n\t\t}\r\n\t\tst.insert((Data){nl,nl+bckt[loc]-1,'a'+loc});\r\n\t\tnl+=bckt[loc];\r\n\t}\r\n\tclr();\r\n}\r\ninline void prnt(){\r\n\tfor(std::set<Data>::iterator it=st.begin();it!=st.end();++it){\r\n\t\tfor(int j=it->l;j<=it->r;++j){\r\n\t\t\tputchar(it->id);\r\n\t\t}\r\n\t}\r\n\tputs(\"\");\r\n}\r\ninline void init(){\r\n\tscanf(\"%d%d\",&n,&q);\r\n\tstd::cin>>ch+1;\r\n\tfor(int i=1;i<=n;++i){\r\n\t\tst.insert((Data){i,i,ch[i]});\r\n\t}\r\n\tint l,r,op;\r\n\tfor(int i=1;i<=q;++i){\r\n\t\tscanf(\"%d%d%d\",&l,&r,&op);\r\n\t\tuni(l,r,op);\r\n\/\/\t\tprnt();\r\n\t}\r\n\tprnt();\r\n}\r\n\r\nint main(){\r\n\tinit();\r\n\treturn 0;\r\n}\r\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u5f00\u4e00\u9897\u73c2\u6735\u8389\u6811\uff0c\u5bf9\u4e8e\u6bcf\u4e2a\u65b0\u7684\u67e5\u8be2\uff0c\u5148\u628al-1,l\u4e4b\u95f4\u548cr,r+1\u4e4b\u95f4split\u5f00\uff0c\u7136\u540e\u5bf9\u4e8e\u5269\u4e0b\u7684\u90e8\u4efd\u7528\u6876\u6392\u5e8f\u5e76 … <\/p>\n