Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"hzoi2017_jjm","updateTime":1546951383000,"title":"Trash Bin","dislikeCnt":0,"content":"### To do 2153,2824\n```cpp\ninline long long mmul ( const long long\u0026 a, const long long\u0026 b ) { \n\tlong long lf \u003d a * ( b \u003e\u003e 20 ) % p * ( 1LL \u003c\u003c 20 ) % p ; \n\tlong long rg \u003d a * ( b \u0026 ( ( 1LL \u003c\u003c 20 ) - 1 ) ) % p ; \n\treturn ( lf + rg ) % p ; \n}\n```\n```cpp\n//EK\ntemplate\u003csize_t N,size_t M\u003e\nclass Graph{\nprivate:\n\tstruct Edge{int y,f,z;Edge*p,*rev;}e[M\u003c\u003c1];\n\tEdge*h[N],*pre[N];\n\tEdge*ec;\n\n\tint d[N];\n\tbool vis[N];\n\n#define y (i-\u003ey)\n#define z (i-\u003ez)\n\t\n\tbool Bfs(int s,int t){\n\t\tmemset(d,0x3f,sizeof d);\n\t\tstatic int Q[N];\n\t\tint*L\u003dQ,*R\u003dQ,*T\u003dQ+N;\n\t\t*R++\u003ds;\n\t\td[s]\u003d0;\n\t\twhile(L!\u003dR){\n\t\t\tint x\u003d*L++;\n\t\t\tif(L\u003d\u003dT)\n\t\t\t\tL\u003dQ;\n\t\t\tvis[x]\u003dfalse;\n\t\t\tfor(Edge*i\u003dh[x];i;i\u003di-\u003ep)\n\t\t\t\tif(d[y]\u003ed[x]+z \u0026\u0026 i-\u003ef){\n\t\t\t\t\td[y]\u003dd[x]+z;\n\t\t\t\t\tpre[y]\u003di;\n\t\t\t\t\tif(!vis[y]){\n\t\t\t\t\t\tvis[y]\u003dtrue;\n\t\t\t\t\t\t*R++\u003dy;\n\t\t\t\t\t\tif(R\u003d\u003dT)\n\t\t\t\t\t\t\tR\u003dQ;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t}\n\t\treturn d[t]!\u003d*d;\n\t}\n\n#undef y\n#undef z\n \npublic:\n\tGraph(){Clear();}\n\tvoid Clear(){memset(h,0,sizeof h);memset(vis,0,sizeof vis);ec\u003de;}\n\tvoid Add(int x,int y,int f,int z){\n\t\tec++;*ec\u003d(Edge){y,f,+z,h[x],ec+1};h[x]\u003dec;\n\t\tec++;*ec\u003d(Edge){x,0,-z,h[y],ec-1};h[y]\u003dec;\n\t}\n\n\tstd::pair\u003cint,int\u003e Ek(int s,int t){\n\t\tint cost\u003d0,flow\u003d0;\n\t\twhile(Bfs(s,t)){\n\t\t\tint f\u003d1\u003c\u003c29;\n\t\t\tfor(Edge*i\u003dpre[t];i;i\u003dpre[i-\u003erev-\u003ey])\n\t\t\t\tf\u003dstd::min(f,i-\u003ef);\n\t\t\tfor(Edge*i\u003dpre[t];i;i\u003dpre[i-\u003erev-\u003ey])\n\t\t\t\ti-\u003ef-\u003df,i-\u003erev-\u003ef+\u003df;\n\t\t\tflow+\u003df;\n\t\t\tcost+\u003dd[t]*f;\n\t\t}\n\t\treturn std::make_pair(flow,cost);\n\t}\n};\n\n```\n```cpp\n#include\u003cbits/stdc++.h\u003e\n\n#define N 210\n#define M N*N\n#define LL long long\n#define Inf (1\u003c\u003c30)\n\nnamespace Prime{\n\tbool vis[100010];\n\tint p[100010];\n\tint pc\u003d0;\n\n\tvoid Getprime(int n){\n\t\tvis[1]\u003dtrue;\n\t\tfor(int i\u003d2;i\u003cn;i++){\n\t\t\tif(!vis[i])\n\t\t\t\tp[++pc]\u003di;\n\t\t\tfor(int j\u003d1;j\u003c\u003dpc \u0026\u0026 1LL*i*p[j]\u003cn;j++){\n\t\t\t\tvis[i*p[j]]\u003dtrue;\n\t\t\t\tif(i%p[j]\u003d\u003d0)\n\t\t\t\t\tbreak;\n\t\t\t}\n\t\t}\n\t}\n\n\tint Count(int x){\n\t\tint ans\u003d0;\n\t\tfor(int i\u003d1;i\u003c\u003dpc;i++)\n\t\t\twhile(x%p[i]\u003d\u003d0)\n\t\t\t\tx/\u003dp[i],ans++;\n\t\tans+\u003d(x\u003e1);\n\t\treturn ans;\n\t}\n\n\tbool Isprime(int x){\n\t\tfor(int i\u003d1;i\u003c\u003dpc;i++)\n\t\t\tif(x%p[i]\u003d\u003d0)\n\t\t\t\treturn false;\n\t\treturn true;\n\t}\n}\n\nusing Prime::Getprime;\nusing Prime::Count;\nusing Prime::Isprime;\n\nstruct Edge{int y,f;LL w;Edge*p,*rev;}e[M\u003c\u003c1];\nEdge*h[N];\nEdge*ec\u003de;\n\nvoid Add(int x,int y,int z,LL w){\n\tec++;*ec\u003d(Edge){y,z,+w,h[x],ec+1};h[x]\u003dec;\n\tec++;*ec\u003d(Edge){x,0,-w,h[y],ec-1};h[y]\u003dec;\n}\n\nLL d[N];\nbool vis[N];\n\n#define y (i-\u003ey)\n#define z (i-\u003ew)\n\nbool Bfs(int s,int t){\n\tstatic int Q[N];\n\tmemset(d,0x3f,sizeof d);\n\tint *L\u003dQ,*R\u003dQ,*T\u003dQ+N;\n\t*R++\u003ds;\n\td[s]\u003d0;\n\twhile(L!\u003dR){\n\t\tint x\u003d*L++;\n\t\tif(L\u003d\u003dT)\n\t\t\tL\u003dQ;\n\t\tfor(Edge*i\u003dh[x];i;i\u003di-\u003ep)\n\t\t\tif(d[y]\u003ed[x]+z \u0026\u0026 i-\u003ef){\n\t\t\t\td[y]\u003dd[x]+z;\n\t\t\t\tif(!vis[y]){\n\t\t\t\t\tvis[y]\u003dtrue;\n\t\t\t\t\t*R++\u003dy;\n\t\t\t\t\tif(R\u003d\u003dT)\n\t\t\t\t\t\tR\u003dQ;\n\t\t\t\t}\n\t\t\t}\n\t}\n\treturn d[t]\u003d\u003dd[0];\n}\n\nint Dfs(int x,int t,int a){\n\tif(x\u003d\u003dt || !a)\n\t\treturn a;\n\tint flow\u003da;\n\tvis[x]\u003dtrue;\n\tfor(Edge*i\u003dh[x];i;i\u003di-\u003ep)\n\t\tif(d[y]\u003d\u003dd[x]+z \u0026\u0026 !vis[y]){\n\t\t\tint f\u003dDfs(y,t,std::min(flow,i-\u003ef));\n\t\t\ti-\u003ef-\u003df;\n\t\t\ti-\u003erev-\u003ef+\u003df;\n\t\t\tflow-\u003df;\n\t\t\tif(!flow)\n\t\t\t\tbreak;\n\t\t}\n\tvis[x]\u003dfalse;\n\treturn a-flow;\n}\n\n#undef y\n#undef z\n\nint a[N],b[N],c[N],u[N],v[N];\n\nint main(){\n\tint n;\n\tscanf(\"%d\",\u0026n);\n\tfor(int i\u003d1;i\u003c\u003dn;i++)\n\t\tscanf(\"%d\",a+i);\n\tfor(int i\u003d1;i\u003c\u003dn;i++)\n\t\tscanf(\"%d\",b+i);\n\tfor(int i\u003d1;i\u003c\u003dn;i++)\n\t\tscanf(\"%d\",c+i);\n\tGetprime(100010);\n\tint uc\u003d0,vc\u003d0;\n\tfor(int i\u003d1;i\u003c\u003dn;i++)\n\t\tif(Count(a[i])\u00261)\n\t\t\tu[++uc]\u003di;\n\t\telse\n\t\t\tv[++vc]\u003di;\n\tint S\u003dn+1,T\u003dS+1;\n\tfor(int i\u003d1;i\u003c\u003duc;i++)\n\t\tAdd(S,i,b[u[i]],0);\n\tfor(int i\u003d1;i\u003c\u003dvc;i++)\n\t\tAdd(i+uc,T,b[v[i]],0);\n\tfor(int i\u003d1;i\u003c\u003duc;i++)\n\t\tfor(int j\u003d1;j\u003c\u003dvc;j++)\n\t\t\tif(Isprime(a[u[i]]/a[v[j]]))\n\t\t\t\tAdd(i,j+uc,Inf,1LL*c[i]*c[j]);\n\tint flow\u003d0;\n\tLL cost\u003d0;\n\twhile(Bfs(S,T)){\n\t\tint t\u003dDfs(S,T,Inf);\n\t\tcost+\u003d1LL*t*d[T];\n\t\tif(cost\u003c0)\n\t\t\tbreak;\n\t\telse\n\t\t\tflow+\u003dt;\n\t}\n\tprintf(\"%d\\n\",flow);\n\treturn 0;\n}\n\n```\n```cpp\n#include\u003cbits/stdc++.h\u003e\n\n#define N 70010\n#define nullptr 0\n\nint a[N];\n\nclass Segment_tree{\nprivate:\n\tstruct Node{\n\t\tNode*ls;\n\t\tNode*rs;\n\t\tint sum;\n\n\t\tNode(){ls\u003drs\u003dnullptr;sum\u003d0;}\n\t};\n\n\tint L,R,w;\n\t\n\tvoid Insert(Node*\u0026p,int l,int r){\n\t\tif(!p)\n\t\t\tp\u003dnew Node();\n\t\tp-\u003esum+\u003dw;\n\t\tif(l\u003d\u003dr)\n\t\t\treturn;\n\t\tint mid\u003dl+r\u003e\u003e1;\n\t\tif(L\u003c\u003dmid)\n\t\t\tInsert(p-\u003els,l,mid);\n\t\telse\n\t\t\tInsert(p-\u003ers,mid+1,r);\n\t}\n\n\tint Query(Node*p,int l,int r){\n\t\tif(!p)\n\t\t\treturn 0;\n\t\tif(l\u003e\u003dL \u0026\u0026 r\u003c\u003dR)\n\t\t\treturn p-\u003esum;\n\t\tint mid\u003dl+r\u003e\u003e1;\n\t\tint ans\u003d0;\n\t\tif(L\u003c\u003dmid)\n\t\t\tans+\u003dQuery(p-\u003els,l,mid);\n\t\tif(R\u003emid)\n\t\t\tans+\u003dQuery(p-\u003ers,mid+1,r);\n\t\treturn ans;\n\t}\n\n\tvoid Print(Node*p,int l,int r){\n\t\tif(!p || p-\u003esum\u003d\u003d0)\n\t\t\treturn;\n\t\tif(l\u003d\u003dr)\n\t\t\treturn printf(\"%d \",l),void();\n\t\tint mid\u003dl+r\u003e\u003e1;\n\t\tPrint(p-\u003els,l,mid);\n\t\tPrint(p-\u003ers,mid+1,r);\n\t}\n\t\n\tNode*rt;\npublic:\n\tSegment_tree(){rt\u003dnullptr;}\n\tvoid Insert(int p){L\u003dp,w\u003d1,Insert(rt,0,70000);}\n\tvoid Erase(int p){L\u003dp,w\u003d-1,Insert(rt,0,70000);}\n\tint Query(int v){return L\u003d0,R\u003dv,Query(rt,0,70000);}\n\tvoid Print(){Print(rt,0,70000);puts(\"\");}\n};\n\nstruct Node{\n\tNode*fa;\n\tNode*ls;\n\tNode*rs;\n\tint siz;\n\tint v;\n Segment_tree t;\n\n\tNode(int w\u003d0){fa\u003dls\u003drs\u003dnullptr;siz\u003d1;v\u003dw;}\n}*rt;\n\nvoid Build(Node*\u0026p,int l,int r){\n\tif(l\u003er)\n\t\treturn;\n\tint mid\u003dl+r\u003e\u003e1;\n\tp\u003dnew Node(a[mid]);\n\tfor(int i\u003dl;i\u003c\u003dr;i++)\n\t\tp-\u003et.Insert(a[i]);\n//\tprintf(\"%d-\u003e\",mid);p-\u003et.Print();\n\tp-\u003esiz\u003dr-l+1;\n\tBuild(p-\u003els,l,mid-1);\n\tBuild(p-\u003ers,mid+1,r);\n\tif(p-\u003els)\n\t\tp-\u003els-\u003efa\u003dp;\n\tif(p-\u003ers)\n\t\tp-\u003ers-\u003efa\u003dp;\n}\n\nbool Bad(Node*p){\n\tint lim\u003dp-\u003esiz*0.7+5;\n\treturn (p-\u003els \u0026\u0026 p-\u003els-\u003esiz\u003e\u003dlim)||(p-\u003ers \u0026\u0026 p-\u003ers-\u003esiz\u003e\u003dlim);\n}\n\nint Getrank(Node*p){\n int cnt\u003d(p-\u003els? p-\u003els-\u003esiz:0)+1;\n\twhile(p-\u003efa){\n\t\tif(p-\u003efa-\u003ers\u003d\u003dp)\n\t\t\tcnt+\u003d(p-\u003efa-\u003els? p-\u003efa-\u003els-\u003esiz:0)+1;\n\t\tp\u003dp-\u003efa;\n\t}\n\treturn cnt;\n}\n\nvoid Dfs(Node*\u0026p){\n\tif(!p)\n\t\treturn;\n\tDfs(p-\u003els);\n\tDfs(p-\u003ers);\n\tdelete p;\n\tp\u003dnullptr;\n}\n\nvoid Rebuild(Node*\u0026p){\n\tint pc\u003d0;\n\tint mid\u003dGetrank(p);\n\tint l\u003d(p-\u003els? mid-p-\u003els-\u003esiz:mid),r\u003d(p-\u003ers? mid+p-\u003ers-\u003esiz:mid);\n\tDfs(p);\n Build(p,l,r);\n}\n\nNode*bad;\n\nvoid Insert(Node*\u0026p,int k,int v){\n\tif(!p){\n\t\tp\u003dnew Node(v);\n\t\tp-\u003et.Insert(v);\n\t\treturn;\n\t}\n\t//printf(\"%d-\u003e%d\\n\",p-\u003ev,k);\n\tint siz\u003dp-\u003els? p-\u003els-\u003esiz:0;\n\tp-\u003et.Insert(v);\n\tif(siz\u003e\u003dk){\n\t\tInsert(p-\u003els,k,v);\n\t\tp-\u003els-\u003efa\u003dp;\n\t}\n\telse{\n\t\tInsert(p-\u003ers,k-siz-1,v);\n\t\tp-\u003ers-\u003efa\u003dp;\n\t}\n\tp-\u003esiz++;\n\tif(Bad(p))\n\t\tbad\u003dp;\n}\n\nvoid Insert(int k,int v){\n\tbad\u003dnullptr;\n\tInsert(rt,k-1,v);\n\tif(bad)\n\t\tRebuild(bad);\n}\n\nNode*Getkth(int k){\n\tif(!k)\n\t\treturn nullptr;\n\tNode*p\u003drt;\n//\tprintf(\"{%d}\\n\",k);\n\twhile(true){\n\t\tint siz\u003d(p-\u003els? p-\u003els-\u003esiz:0)+1;\n\t\t//\tif(siz\u003d\u003dk)printf(\"[%d]\\n\",p-\u003ev);\n\t\tif(siz\u003d\u003dk)\n\t\t\treturn p;\n\t\telse if(siz\u003ck)\n\t\t\tk-\u003dsiz,p\u003dp-\u003ers;\n\t\telse\n\t\t\tp\u003dp-\u003els;\n\t}\n}\n\nvoid Modify(int k,int v){\n\tNode*p\u003dGetkth(k);\n\tint w\u003dp-\u003ev;\n\tprintf(\"%d\\n\",w);\n\tp-\u003ev\u003dv;\n\tp-\u003et.Erase(w);\n\tp-\u003et.Insert(v);\n\twhile(p-\u003efa){\n\t\tp\u003dp-\u003efa;\n\t\tprintf(\"%d\\n\",p-\u003ev);\n\t\tp-\u003et.Erase(w);\n\t\tp-\u003et.Insert(v);\n\t}\n\tputs(\"\");\n}\n\nbool fir\u003dfalse;\n\nint Get(int k,Node*p){//leq\n\tif(!p)\n\t\treturn 0;\n int cnt\u003d0;\n\tif(p-\u003els)\n\t\tcnt+\u003dp-\u003els-\u003et.Query(k);\n\tcnt+\u003d(p-\u003ev\u003c\u003dk);\n\tif(fir)printf(\"%d\\n\",p-\u003ev);\n\twhile(p-\u003efa){\n\t\tif(fir)\n\t\t\tprintf(\"%d | %d\\n\",p-\u003ev,p-\u003efa-\u003ev);\n\t\tif(p-\u003efa-\u003ers\u003d\u003dp){\n\t\t\tcnt+\u003d(p-\u003efa-\u003ev\u003c\u003dk);\n\t\t\tif(p-\u003els){\n\t\t\t\tif(fir)\n\t\t\t\t\tprintf(\"{%d}\\n\",p-\u003efa-\u003els-\u003ev);\n\t\t\t\tcnt+\u003dp-\u003els-\u003et.Query(k);\n\t\t\t}\n\t\t}\n\t\tp\u003dp-\u003efa;\n\t}\n\tfir\u003dfalse;\n\treturn cnt;\n}\n\nint Query(int l,int r,int k){\n\tint L\u003d0,R\u003d70000;\n\tR\u003d50;\n\tNode*s\u003dGetkth(l-1),*t\u003dGetkth(r);\n\tprintf(\"%d %d\\n\",s-\u003ev,t-\u003ev);\n\twhile(L\u003c\u003dR){\n\t\tint mid\u003dL+R\u003e\u003e1;\n\t\tGet(mid,t);\n\t\tprintf(\"%d -\u003e %d,%d\\n\",mid,Get(mid,t),Get(mid,s));\n\t\tif(Get(mid,t)-Get(mid,s)\u003e\u003dk)\n\t\t\tR\u003dmid-1;\n\t\telse\n\t\t\tL\u003dmid+1;\n\t}\n\treturn L;\n}\n\nint main(){\n\tint n;\n\tscanf(\"%d\",\u0026n);\n\tfor(int i\u003d1;i\u003c\u003dn;i++)\n\t\tscanf(\"%d\",a+i);\n\tBuild(rt,1,n);\n\tint q;\n\tscanf(\"%d\",\u0026q);\n for(int op,x,y,k,ans\u003d0;q--;){\n\t\twhile((op\u003dgetchar())\u003c\u0027!\u0027){}\n\t\tif(op\u003d\u003d\u0027Q\u0027){\n\t\t\tscanf(\"%d%d%d\",\u0026x,\u0026y,\u0026k);\n\t\t\tx^\u003dans,y^\u003dans,k^\u003dans;\n\t\t\tprintf(\"%d\\n\",ans\u003dQuery(x,y,k));\n\t\t}\n\t\telse if(op\u003d\u003d\u0027M\u0027)\n\t\t\tscanf(\"%d%d\",\u0026x,\u0026k),x^\u003dans,k^\u003dans,Modify(x,k);\n\t\telse\n\t\t\tscanf(\"%d%d\",\u0026x,\u0026k),x^\u003dans,k^\u003dans,Insert(x,k);\n\t\t//puts(\"Finished!\");\n\t}\n\treturn 0;\n}\n\n\n\n```\n```cpp\n#include\u003cbits/stdc++.h\u003e\n\n#define N 100100\n#define M 100100\ntemplate\u003cclass T\u003einline void Smin(T\u0026a,T b){a\u003da\u003cb?a:b;}\n\nstruct Edge{int y,z;Edge*p;}e[M\u003c\u003c1];\nEdge*h[N],*H[N];\nEdge*ec\u003de;\n\nint t,pc;\nbool vis[N];\nint d[102][N];\nint sp[102];\nint dep[N],fa[N],siz[N],son[N],top[N],a[N],dis[N];\n\nvoid Add(int x,int y,int z,Edge**h){*++ec\u003d(Edge){y,z,h[x]},h[x]\u003dec;}\n\nint Find(int x){return a[x]\u003d\u003dx? x:a[x]\u003dFind(a[x]);}\n\n#define y (i-\u003ey)\n#define z (i-\u003ez)\n\nvoid Dijkstra(int pos){\n int *d\u003d::d[pos];\n int s\u003dsp[pos];\n Node*q\u003dp;\n *q++\u003d(Node){s,d[s]\u003d0};\n memset(vis,false,sizeof vis);\n while(p!\u003dq){\n int x\u003dp-\u003ex;\n std::pop_heap(p,q--);\n if(vis[x])\n continue;\n vis[x]\u003dtrue;\n for(Edge*i\u003dH[x];i;i\u003di-\u003ep)\n if(d[y]\u003ed[x]+z)\n d[y]\u003dd[x]+z,*q++\u003d(Node){y,d[y]},std::push_heap(p,q);\n }\n}\n\nvoid Dfs(int x,int f,int d){\n x[fa]\u003df;\n x[dep]\u003d1;\n x[siz]\u003d1;\n for(Edeg*i\u003dh[x];i;i\u003di-\u003ep){\n if(y\u003d\u003df)\n continue;\n y[dis]\u003dx[dis]+z;\n Dfs(y,x,d+1);\n if(x[son][siz]\u003cy[siz])\n x[son]\u003dy;\n }\n}\n\nvoid Dfs(int x,int tp){\n x[top]\u003dtp;\n if(x[son])\n Dfs(x[son],tp);\n for(Edge*i\u003dh[x];i;i\u003di-\u003ep)\n if(y!\u003dx[fa] \u0026\u0026 y!\u003dx[son])\n Dfs(y,y);\n}\n\n#undef y\n#undef z\n\nint Lca(int x,int y){\n while(x[top]!\u003dy[top]){\n if(x[top][dep]\u003cy[top][dep])\n Swap(x,y);\n x\u003dx[top][fa];\n }\n if(x[dep]\u003ey[dep])\n Swap(x,y);\n return x;\n}\n\nint Query(int x,int y){\n int ans\u003ddis[x]+dis[y]-(dis[Lca(x,y)]\u003c\u003c1);\n for(int i\u003d1;i\u003c\u003dpc;i++)\n Smin(ans,d[sp[i]][x]+d[sp[i]][y]);\n return ans;\n}\n\nvoid Init(){\n memset(h,0,sizeof h);\n memset(H,0,sizeof H);\n memset(vis,0,sizeof vis);\n memset(son,0,sizeof son);\n memset(d,0x3f,sizeof d);\n ec\u003de;\n t\u003d0;\n pc\u003d0;\n for(int i\u003d1;i\u003cN;i++)\n a[i]\u003di;\n}\n\nvoid Solve(){\n int n,m,q;\n scanf(\"%d%d%d\",\u0026n,\u0026m,\u0026q);\n for(int i\u003d1,x,y,z;i\u003c\u003dm;i++){\n scanf(\"%d%d%d\",\u0026x,\u0026y,\u0026z);\n Add(x,y,z,H);\n if(Find(x)!\u003dFind(y))\n a[Find(x)]\u003dFind(y),Add(x,y,z,H);\n else\n vis[x]\u003dvis[y]\u003dtrue;\n }\n for(int i\u003d1;i\u003c\u003dn;i++)\n\t\tif(!vis[i])\n\t\t\tsp[++pc]\u003di,Dijkstra(pc);\n Dfs(1,0,0);\n Dfs(1,1);\n for(int x,y;q--;){\n\t\tscanf(\"%d%d\",\u0026x,\u0026y);\n\t printf(\"%d\\n\",Query(x,y));\n\t}\n}\n\nint main(){\n int T;\n scanf(\"%d\",\u0026T);\n while(T--)\n Init(),Solve();\n return 0;\n}\n\n```\n```cpp\nw#include\u003cbits/stdc++.h\u003e\n\n#define N 200010\n#define M 200010\n\nstruct Pair{\n\tint l,r,len;\n\tPair(){}\n\tPair(int l,int r,int len\u003dr-l+1):l(l),r(r),len(len){};\n};\n\nbool operator \u003c(const Pair\u0026lhs,const Pair\u0026rhs){return lhs.l\u003crhs.l;}\n\nstruct Edge{int y;Edge*p;}e[M\u003c\u003c1];\nEdge*h[N];\nEdge*ec\u003de;\n\nint w[N],pos[N];\nlong long ans\u003d0;\nlong long c[N];\nstd::set\u003cPair\u003e s[N];\n\nvoid Add(int x,int y){*++ec\u003d(Edge){y,h[x]},h[x]\u003dec;}\n\n#define y (i-\u003ey)\n\ninline long long C(int x){return 1LL*x*(x+1)/2;}\n\nvoid Dfs(int x){\n\ts[x].insert(Pair(pos[x],pos[x]));\n\tc[x]\u003d1;\n\tlong long siz\u003d0;\n\tfor(Edge*i\u003dh[x];i;i\u003di-\u003ep){\n\t\tDfs(y);\n\t\tsiz+\u003dc[y];\n\t\tif(s[x].size()\u003cs[y].size())\n\t\t\tstd::swap(s[x],s[y]),std::swap(c[x],c[y]);\n\t\tfor(std::set\u003cPair\u003e::iterator it\u003ds[y].begin(),l,r;it!\u003ds[y].end();++it){\n\t\t\tl\u003dr\u003ds[x].lower_bound(*it);\n\t\t\tif(r!\u003ds[x].begin())\n\t\t\t\t--l;\n\t\t\tif(r\u003d\u003ds[x].begin()){\n\t\t\t\tif(it-\u003er+1\u003d\u003dr-\u003el){\n\t\t\t\t\tc[x]-\u003dC(r-\u003elen);\n\t\t\t\t\tc[x]+\u003dC(it-\u003elen+r-\u003elen);\n\t\t\t\t\ts[x].insert(Pair(it-\u003el,it-\u003el+it-\u003elen+r-\u003elen-1));\n\t\t\t\t\ts[x].erase(r);\n\t\t\t\t}\n\t\t\t\telse{\n\t\t\t\t\tc[x]+\u003dC(it-\u003elen);\n\t\t\t\t\ts[x].insert(*it);\n\t\t\t\t}\n\t\t\t}\n\t\t\telse if(r\u003d\u003ds[x].end()){\n\t\t\t\tif(l-\u003er+1\u003d\u003dit-\u003el){\n\t\t\t\t\tc[x]-\u003dC(l-\u003elen);\n\t\t\t\t\tc[x]+\u003d(it-\u003elen+l-\u003elen);\n\t\t\t\t\ts[x].insert(Pair(l-\u003el,l-\u003el+l-\u003elen+it-\u003elen-1));\n\t\t\t\t\ts[x].erase(l);\n\t\t\t\t}\n\t\t\t\telse{\n\t\t\t\t\tc[x]+\u003dC(it-\u003elen);\n\t\t\t\t\ts[x].insert(*it);\n\t\t\t\t}\n\t\t\t}\n\t\t\telse if(l-\u003er+1\u003d\u003dit-\u003el \u0026\u0026 it-\u003er+1\u003d\u003dr-\u003el){\n\t\t\t\tc[x]-\u003dC(l-\u003elen);\n\t\t\t\tc[x]-\u003dC(r-\u003elen);\n\t\t\t\tc[x]+\u003dC(l-\u003elen+it-\u003elen+r-\u003elen);\n\t\t\t\ts[x].insert(Pair(l-\u003el,l-\u003el+l-\u003elen+r-\u003elen+it-\u003elen-1));\n\t\t\t\ts[x].erase(l);\n\t\t\t\ts[x].erase(r);\n\t\t\t}\n\t\t\telse if(l-\u003er+1\u003d\u003dit-\u003el){\n\t\t\t\tc[x]-\u003dC(l-\u003elen);\n\t\t\t\tc[x]+\u003dC(l-\u003elen+it-\u003elen);\n\t\t\t\ts[x].insert(Pair(l-\u003el,l-\u003el+l-\u003elen+it-\u003elen-1));\n\t\t\t\ts[x].erase(l);\n\t\t\t}\n\t\t\telse if(it-\u003er+1\u003d\u003dr-\u003el){\n\t\t\t\tc[x]-\u003dC(r-\u003elen);\n\t\t\t\tc[x]+\u003dC(it-\u003elen+r-\u003elen);\n\t\t\t\ts[x].insert(Pair(it-\u003el,it-\u003el+it-\u003elen+r-\u003elen-1));\n\t\t\t\ts[x].erase(r);\n\t\t\t}\n\t\t\telse{\n\t\t\t\tc[x]+\u003dC(it-\u003elen);\n\t\t\t\ts[x].insert(*it);\n\t\t\t}\n\t\t}\n\t}\n\tans+\u003d(c[x]-siz)*w[x];\n\tprintf(\"%d-\u003e%lld\\n\",x,c[x]-siz);\n}\n\n#undef y\n\nint main(){\n\tint n;\n scanf(\"%d\",\u0026n);\n\tfor(int i\u003d2,x;i\u003c\u003dn;i++)\n\t\tscanf(\"%d\",\u0026x),Add(x,i);\n\tfor(int i\u003d1,x;i\u003c\u003dn;i++)\n\t\tscanf(\"%d\",\u0026x),pos[x]\u003di;\n\tfor(int i\u003d1;i\u003c\u003dn;i++)\n\t\tscanf(\"%d\",w+i);\n Dfs(1);\n\tprintf(\"%lld\\n\",ans);\n\treturn 0;\n}\n\n```\n```cpp\n#include\u003cbits/stdc++.h\u003e\n\n#define N 100100\n#define M 100100\n\nstruct Edge{int y,z;Edge*p;}e[M\u003c\u003c1];\nEdge*h[N],H[N];\nEdge*ec\u003de;\n\nint t,pc;\nbool vis[N];\nint d[52][N];\nint sp[52];\nint dep[N],fa[N],siz[N],son[N],top[N],a[N],dis[N];\n\nvoid Add(int x,int y,int z,Edge**h){*++ec\u003d(Edge){y,z,h[x]},h[x]\u003dec;}\n\nint Find(int x){return a[x]\u003d\u003dx? x:a[x]\u003dFind(a[x]);}\n\n#define y (i-\u003ey)\n#define z (i-\u003ez)\n\nvoid Dijkstra(int pos){\n\tint *d\u003d::d[pos];\n\tint s\u003dsp[pos];\n\tNode*q\u003dp;\n\t*q++\u003d(Node){s,d[s]\u003d0};\n\tmemset(vis,false,sizeof vis);\n\twhile(p!\u003dq){\n\t\tint x\u003dp-\u003ex;\n\t\tstd::pop_heap(p,q--);\n\t\tif(vis[x])\n\t\t\tcontinue;\n\t\tvis[x]\u003dtrue;\n\t for(Edge*i\u003dH[x];i;i\u003di-\u003ep)\n\t\t\tif(d[y]\u003ed[x]+z)\n\t\t\t\td[y]\u003dd[x]+z,*q++\u003d(Node){y,d[y]},std::push_heap(p,q);\n\t}\n}\n\nvoid Dfs(int x,int f,int d){\n\tx[fa]\u003df;\n\tx[dep]\u003d1;\n\tx[siz]\u003d1;\n\tfor(Edeg*i\u003dh[x];i;i\u003di-\u003ep){\n\t\tif(y\u003d\u003df)\n\t\t\tcontinue;\n\t\ty[dis]\u003dx[dis]+z;\n\t\tDfs(y,x,d+1);\n\t\tif(x[son][siz]\u003cy[siz])\n\t\t\tx[son]\u003dy;\n\t}\n}\n\nvoid Dfs(int x,int tp){\n\tx[top]\u003dtp;\n\tif(x[son])\n\t Dfs(x[son],tp);\n\tfor(Edge*i\u003dh[x];i;i\u003di-\u003ep)\n\t\tif(y!\u003dx[fa] \u0026\u0026 y!\u003dx[son])\n\t\t\tDfs(y,y);\n}\n\n#undef y\n#undef z\n\nint Lca(int x,int y){\n\twhile(x[top]!\u003dy[top]){\n\t\tif(x[top][dep]\u003cy[top][dep])\n\t\t\tSwap(x,y);\n\t\tx\u003dx[top][fa];\n\t}\n\tif(x[dep]\u003ey[dep])\n\t\tSwap(x,y);\n\treturn x;\n}\n\nint Query(int x,int y){\n\tint ans\u003ddis[x]+dis[y]-(dis[Lca(x,y)]\u003c\u003c1);\n for(int i\u003d1;i\u003c\u003dsp;i++)\n\t\tSmin(ans,d[i][x]+d[i][y]);\n\treturn ans;\n}\n\nvoid Init(){\n\tmemset(h,0,sizeof h);\n\tmemset(H,0,sizeof H);\n\tmemset(vis,0,sizeof vis);\n\tmemset(son,0,sizeof son);\n\tmemset(d,0x3f,sizeof d);\n\tec\u003de;\n\tt\u003d0;\n\tpc\u003d0;\n\tfor(int i\u003d1;i\u003cN;i++)\n\t\ta[i]\u003di;\n}\n\nvoid Solve(){\n\tint n,m,q;\n\tscanf(\"%d%d%d\",\u0026n,\u0026m,\u0026q);\n\tfor(int i\u003d1,x,y;i\u003c\u003dm;i++){\n\t\tscanf(\"%d%d%d\",\u0026x,\u0026y,\u0026z);\n\t\tAdd(x,y,z,H);\n\t\tif(Find(x)!\u003dFind(y))\n\t\t\ta[Find(x)]\u003dFind(y),Add(x,y,z,H);\n\t\telse\n\t\t\tsp[x]\u003dsp[y]\u003dtrue;\n\t}\n\tfor(int i\u003d1;i\u003c\u003dn;i++h)\n Dfs(1,0,0);\n Dfs(1,1);\n\tfor(int )\n}\n\nint main(){\n\tint T;\n\tscanf(\"%d\",\u0026T);\n\twhile(T--)\n\t\tInit(),Solve();\n\treturn 0;\n}\n\n```\n```cpp\n#include\u003cbits/stdc++.h\u003e\n\n#define N 200010\n#define M 400010\n#define nullptr 0\n\ntemplate\u003cclass T\u003e\nstruct Treapnode{\n\tint siz;\n\tint pri;\n\tTreapnode*ls;\n\tTreapnode*rs;\n\tT v;\n\n\tTreapnode(){}\n\tTreapnode(T v):siz(1),pri(rand()),ls(nullptr),rs(nullptr),v(v){}\n\tint Size(){return this\u003d\u003dnullptr? 0:siz;}\n\tvoid Maintain(){siz\u003d1+ls-\u003eSize()+rs-\u003eSize();}\n};\n\n#warning Type!\nTreapnode\u003cint\u003e mem[N\u003c\u003c5],*C\u003dmem;\n\ntemplate\u003cclass T\u003e\nTreapnode\u003cT\u003e*Newnode(T v){\n\tC-\u003esiz\u003d1;\n\tC-\u003epri\u003drand();\n\tC-\u003els\u003dC-\u003ers\u003dnullptr;\n\tC-\u003ev\u003dv;\n\treturn C++;\n}\ntemplate\u003cclass T\u003e\nTreapnode\u003cT\u003e*Newnode(Treapnode\u003cT\u003ep){\n\t*C\u003d*p;\n\treturn C++;\n}\n\n#define Node Treapnode\u003cT\u003e\n\ntemplate\u003cclass T\u003e\nclass Treap{\nprivate:\n\tNode*rt;\n\t\n\tstruct Pair{Node*first,*second;};\n\n\tPair Split(Node*p,int k){\n\t\tif(!p)\n\t\t\treturn (Pair){nullptr,nullptr};\n\t\tNode*q\u003dNewnode(*p);\n\t\tif(p-\u003els-\u003eSize()\u003e\u003dk){\n\t\t\tPair x\u003dSplit(p-\u003ers,k);\n\t\t\tq-\u003ers\u003dx.second;\n\t\t\tq-\u003eMaintain();\n\t\t\tx.second\u003dq;\n\t\t\treturn x;\n\t\t}\n\t\telse{\n\t\t\tPair x\u003dSplit(p-\u003els,k-1-p-\u003els-\u003eSize());\n\t\t\tq-\u003els\u003dx.first;\n\t\t\tq-\u003eMaintain();\n\t\t\tx.first\u003dq;\n\t\t\treturn x;\n\t\t}\n\t}\n\n\tNode*Merge(Node*a,Node*b){\n\t\tif(!a)\n\t\t\treturn b;\n\t\tif(!b)\n\t\t\treturn a;\n\t\tif(a-\u003epri\u003cb-\u003epri){\n\t\t\tNode*p\u003dNewnode(*a);\n\t\t\tp-\u003ers\u003dMerge(p-\u003ers,b);\n\t\t\tp-\u003eMaintain();\n\t\t\treturn p;\n\t\t}\n\t\telse{\n\t\t\tNode*p\u003dNewnode(*b);\n\t\t\tp-\u003els\u003dMerge(a,b-\u003els);\n\t\t\tp-\u003eMaintain();\n\t\t\treturn p;\n\t\t}\n\t}\npublic:\n\tTreap(Node*p\u003dnullptr){rt\u003dp;}\n\tconst T \u0026operator[](int k){\n\t\tfor(Node*p\u003drt;;){\n\t\t\tif(p-\u003els-\u003eSize()\u003d\u003dk-1)\n\t\t\t\treturn p-\u003ev;\n\t\t\tif(p-\u003els-\u003eSize()\u003ck-1)\n\t\t\t\tk-\u003dp-\u003els-\u003eSize(),p\u003dp-\u003ers;\n\t\t\telse\n\t\t\t\tp\u003dp-\u003els;\n\t\t}\n\t}\n\n\tvoid Modify(int k,T v){\n\t\tPair x\u003dSplit(rt,k-1),y\u003dSplit(x.second,1);\n\t\treturn Merge(Merge(x.first,Newnode(v)),y.second);\n\t}\n\t\n\tvoid Insert(int k,T v){\n\t\tPair x\u003dSplit(rt,k);\n\t\treturn Merge(Merge(x.first,Newnode(v)),x.second);\n\t}\n};\n\n\n\nstruct Edge{int y,z;Edge*p;}E[M\u003c\u003c1];\nEdge*h[N];\nEdge*ec\u003dE;\n\nvoid Add(int x,int y,int z){*++ec\u003d(Edge){y,z,h[x]},h[x]\u003dec;}\n\nvoid Init(){\n\tC\u003dmem;\n\tmemset(h,0,sizeof h);\n\tec\u003de;\n}\n\nvoid Solve(){\n\tint n,m;\n\tscanf(\"%d%d\",\u0026n,\u0026m);\n\tfor(int i\u003d1;i\u003c\u003dm;i++)\n\t\tscanf(\"%d%d%d%d\",\u0026x,\u0026y,\u0026z,\u0026w),Add(x,y,z),Add(y,x,z),e[i]\u003d(Edge_){x,y,w};\n\tstd::sort(e+1,e+1+m);\n\tDijkstra();\n\tfor(int i\u003d1;i\u003c\u003dm;i++)\n\t\t\n}\n\nint main(){\n\tint T;\n\tfor(scanf(\"%d\",\u0026T);T--;)\n\t\tInit(),Solve();\n}\n\n```\n```cpp\n#include\u003cbits/stdc++.h\u003e\n\n#define N 200010\n#define LL unsigned long long\n#define P 131\n\nint a[N];\n\ntemplate\u003cclass T\u003e\nclass Segment_tree{\nprivate:\n\tstruct Node{\n\t\tint l;\n\t\tint r;\n\t\tNode*ls;\n\t\tNode*rs;\n\t\tT v;\n\t\tint s;\n\t};\n\n\tNode*Newnode(int l,int r){\n\t\tC-\u003el\u003dl;\n\t\tC-\u003er\u003dr;\n\t\tC-\u003e\n\t}\n\t\n\t\n\t\n\n};\n\nint main(){\n\tint n,m,k;\n\tscanf(\"%d%d%d\",\u0026n,\u0026m,\u0026k);\n\tfor(int i\u003d1;i\u003c\u003dn;i++){\n\t\twhile((a[i]\u003dgetchar())\u003c\u0027!\u0027){}\n\t\ta[i]-\u003d\u00270\u0027;\n\t}\n\tfor(int i\u003dp[0]\u003d1;i\u003c\u003dn;i++)\n\t\tp[i]\u003dp[i-1]*P;\n\tm+\u003dk;\n t.Build(1,n,a);\n for(int op,l,r,d;m--;){\n\t\tscanf(\"%d%d%d%d\",\u0026op,\u0026l,\u0026r,\u0026d);\n\t\tif(op\u003d\u003d1)\n\t\t\tt.Modify(l,r,d);\n\t\telse\n\t\t\tif(d\u003d\u003dr-l+1)\n\t\t\t\tputs(\"YES\");\n\t\t\telse\n\t\t\t\tputs(t.Query(l,r-d)\u003d\u003dt.Query(l+d,r)? \"YES\":\"NO\");\n\t}\n\treturn 0;\n}\n```\n\n\n```cpp\n#include\u003cbits/stdc++.h\u003e\n\n#define Unknown 0\n#define Zhugong 1\n#define Zhongchen 2\n#define Fanzei 3\n#define Leifanzei 4\n#define Sha 1\n#define Shan 2\n#define Tao 3\n#define Juedou 4\n#define Nanman 5\n#define Wanjian 6\n#define Wuxie 7\n#define Zhuge 8\n\nstruct Player{\n\tint hp;\n\tint identity;\n\tint real_identity;\n\tstd::vector\u003cint\u003e cards;\n\tbool weapon;\n}a[15];\n\nstd::map\u003cstd::string,int\u003e hash;\nstd::vector\u003cint\u003e heap;\n\nint Getcard(){\n\tif(heap.size()\u003d\u003d1)\n\t\treturn heap[0];\n\telse{\n\t\tint x\u003dheap.back();\n\t\theap.pop_back();\n\t\treturn x;\n\t}\n}\n\nint n,m;\n\nvoid Init(){\n\thash[\"K\"]\u003dSha;\n\thash[\"P\"]\u003dTao;\n\thash[\"D\"]\u003dShan;\n\thash[\"F\"]\u003dJuedou;\n\thash[\"N\"]\u003dNanman;\n\thash[\"W\"]\u003dWanjian;\n\thash[\"J\"]\u003dWuxie;\n\thash[\"Z\"]\u003dZhuge;\n\thash[\"MP\"]\u003dZhugong;\n\thash[\"ZP\"]\u003dZhongchen;\n\thash[\"FP\"]\u003dFanzei;\n\tscanf(\"%d%d\",\u0026n,\u0026m);\n\ta[0].identity\u003d1;\n\tfor(int i\u003d0;i\u003cn;i++){\n\t\tchar s[10];\n\t\tscanf(\"%s\",s);\n\t\ta[i].real_identity\u003dhash[s];\n\t\tfor(int j\u003d1;j\u003c\u003d4;j++)\n\t\t\tscanf(\"%s\",s),a[i].cards.push_back(hash[s]);\n\t\ta[i].hp\u003d4;\n\t\ta[i].identity\u003dUnknown;\n\t\ta[i].weapon\u003dfalse;\n\t}\n}\n\nbool Differ(int x,int y){//x uses a card to y\n\tif(!a[y].hp)\n\t\treturn false;\n\tif(!a[y].identity)\n\t\treturn false;\n\tint u\u003da[x].real_identity,v\u003da[y].identity;\n\tif(u\u003d\u003dZhugong \u0026\u0026 v\u003d\u003dLeifanzei)\n\t\treturn true;\n\tif(u\u003d\u003dZhugong \u0026\u0026 v\u003d\u003dFanzei)\n\t\treturn true;\n\tif(u\u003d\u003dZhongchen \u0026\u0026 v\u003d\u003dFanzei)\n\t\treturn true;\n\tif(u\u003d\u003dFanzei \u0026\u0026 v\u003d\u003dZhugong)\n\t\treturn true;\n\tif(u\u003d\u003dFanzei \u0026\u0026 v\u003d\u003dZhugong)\n\t\treturn true;\n\tif(u\u003d\u003dFanzei \u0026\u0026 v\u003d\u003dZhongchen)\n\t\treturn true;\n\treturn false;\n}\n\nvoid Damage(int x,int y){\n\t--a[y].hp;\n\tif()\n}\n\nvoid Play(int x,int y,int card){\n\tint p;\n\tif(card\u003d\u003dSha){\n\t\tif(p\u003dHave(y,Shan),p)\n\t\t\tDiscard(y,p);\n\t\telse\n\t\t\tDamage(x,y);\n\t\treturn;\n\t}\n\tif(card\u003d\u003dNanman){\n\t\tint cnt\u003d0;\n\t\tfor(int i\u003d(x+1)%n;cnt\u003c\u003dn;i\u003d(i+1)%n,cnt++){\n\t\t\tif(i\u003d\u003dx)\n\t\t\t\tcontinue;\n\t\t\telse\n\t\t}\n\t}\n\n}\n\nbool Canattack(int x,int y){\n\tif(!Differ(x,y))\n\t\treturn false;\n\tint cnt\u003d0,dis\u003d100;\n\tint u\u003dx,v\u003dy;\n\twhile(u!\u003dv){\n\t\tu++;\n\t\tif(u\u003d\u003dn)\n\t\t\tu\u003d0;\n\t\tif(a[u].hp)\n\t\t\tcnt++;\n\t}\n\twhile(u!\u003dv)\n}\n\nint Canplay(int x,int card){\n\tif(card\u003d\u003dShan || card\u003d\u003dWuxie)\n\t\treturn false;\n\tif(card\u003d\u003dTao \u0026\u0026 a[x].hp!\u003d4)\n\t\treturn true;\n\tif(card\u003d\u003dNanman || card\u003d\u003dWanjian)\n\t\treturn true;\n\tif(card\u003d\u003dZhuge)\n\t\treturn true;\n\tif(card\u003d\u003dSha)\n\t\tif(a[i].weapon || (!a[i].played)){\n\t\t\tfor(int i\u003d0;i\u003cn;i++)\n\t\t\t\tif(Canattack(x,i))\n\t\t\t\t\treturn i;\n\t\t\treturn false;\n\t\t}\n\t\telse\n\t\t\treturn false;\n\tif(card\u003d\u003dJuedou){\n\t\tfor(int i\u003d0;i\u003cn;i++)\n\t\t\tif(Differ(x,i))\n\t\t\t\treturn i;\n\t\treturn false;\n\t}\n}\n\n// return the number of target (if so)\n\nvoid Play(int x){\n\twhile(a[x].cards.size()){\n\t\tbool any\u003dfalse;\n\t\tfor(unsigned i\u003d0;i\u003ca[x].cards.size();i++){\n\t\t\tint card\u003da[x].cards[i],y;\n\t\t\tif(y\u003dCanplay(x,card),y){\n\t\t\t\tany\u003dtrue;\n\t\t\t\tPlay(x,y,card);\n\t\t\t\ta[x].cards.erase(a[x].cards.begin()+i);\n\t\t\t\tbreak;\n\t\t\t}\n\t\t}\n\t\tif(any)\n\t\t\tcontinue;\n\t\telse\n\t\t\tbreak;\n\t}\n}\n\nvoid Drawcards(int x,int num){\n\tfor(int i\u003d1;i\u003c\u003dnum;i++)\n\t\ta[x].cards.push_back(Getcard());\n}\n\nvoid Solve(){\n\tint cur\u003d0;\n\twhile(true){\n\t\tif(!a[cur].hp)\n\t\t\tcontinue;\n\t\tDrawcards(cur,2);\n\t\tPlay(cur);\n\t\tcur++;\n\t\tcur%\u003dn;\n\t}\n}\n\nint main(){\n\tInit();\n\tSolve();\n\treturn 0;\n}\n\n//Everything is zero indexed\n\n```","likeCnt":1,"createTime":1529453049000,"isWorkbook":false,"viewCnt":1458,"openness":1,"fav":false,"id":483,"trustable":false}