鉛導體
問題描述 何老板要求第三題要很簡單，最好是鉛導體的難度。 于是，nodgd把N個鉛塊用N?1根導線相連，就形成了一個鉛導體。只要是在這個基礎上出題，就符合何老板的要求。nodgd為了方便，就把其中的一個鉛塊固定在了墻上，其他鉛塊在導線的作用下自然下垂。每個鉛塊有個固定的純度，若干個相同純度的鉛塊可以聚變發電，發電的電壓與鉛塊的數量成正比。每當nodgd需要電療的時候，就在鉛導體上選一個鉛塊，把它和掛在它下面的所有鉛塊都取下來，在這當中選一些純度相同的鉛塊發電，發電之后將這些鉛塊掛回原來的位置。nodgd希望電療的電壓越高越好，在電壓相同的情況下，nodgd又希望使用純度更低的鉛塊。 但是ciocio經常來搗亂，他時不時的把整個鉛導體取下來，重新選一個鉛塊固定到墻上，其他的鉛塊繼續自然下垂。那么問題來了，nodgd每次都想享受最高電壓的電療，需要你大聲喊出應該使用多少個純度是多 少的鉛塊。
輸入格式 輸入文件C.in。 第一行四個整數N, A, Q, I，表示鉛塊的數量、鉛塊純度的范圍、操作的總次數、測試點編號。 鉛塊按1 ～ N編號，一開始nodgd把編號為1的鉛塊固定在墻上。鉛塊的純度是1 ～ A之間的一個整 數。 接下來N ? 1行，每行兩個整數u, v，表示有一條導線連接。 接下來一行，N個整數，表示每個鉛塊的純度。 接下來Q行，每行輸入兩個整數op, u。 若op = 1，表示ciocio把整個鉛導體取下來，再把編號為u的鉛塊重新固定在墻上。 若op = 2，表示nodgd把編號為u的鉛塊以及掛在他下面的所有鉛塊暫時取下來，選出其中一些鉛塊進行聚變發電。如果要求該組測試點要求強制在線，設上一次輸出的答案兩個數分別為lasta和lastb，則u′ = (u+lasta×23 + lastb×233)%N + 1才是真正的節點編號。
輸出格式 輸出文件C.out。 每次op = 2的時候輸出一行，兩個整數，分別是使用鉛塊的純度和數量。
樣例輸入 5 3 8 0 1 2 1 3 3 4 3 5 1 1 2 2 3 2 3 2 1 2 5 1 3 2 4 2 2 2 1 2 3
樣例輸出 2 2 1 2 3 1 2 1 1 1 1 2 1 2
數據范圍 
dfs序+分塊求眾數，很機智的一個做法將新編號對應的純度數組復制一遍，處理根在子樹內就會方便很多。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstdlib>#include<cstring>#include<cmath>#define ll long longusing namespace std;const int base=500;template <typename T>inline void _read(T& x){ char t=getchar();bool sign=true; while(t<'0'||t>'9'){if(t=='-')sign=false;t=getchar();} for(x=0;t>='0'&&t<='9';t=getchar())x=x*10+t-'0'; if(!sign)x=-x;}int n,m,q,I,N,S;int tot,e,root;int lasta,lastb;int vistime;struct line{ int from,to; line(){} line(int x,int y){from=x;to=y;}};line edge[200005];int last[100005],_next[200005];void add_edge(int x,int y){ edge[++e]=line(x,y); _next[e]=last[x]; last[x]=e;}int father[100005],dep[100005],p[100005][35],id[100005],R[100005],purity[100005],a[100005];void dfs(int x,int fa){ int i,j,k,v; id[x]=++vistime; dep[x]=dep[fa]+1; father[x]=fa; k=ceil(log(dep[x])/log(2)); p[x][0]=fa; for(i=1;i<=k;i++)p[x][i]=p[p[x][i-1]][i-1]; for(i=last[x];i;i=_next[i]){ v=edge[i].to; if(v==fa)continue; dfs(v,x); } R[x]=vistime;}struct node{ int Purity,sum; node(){} node(int x,int y){Purity=x;sum=y;}};node block[605][1005];int cnt[100005];int all[605][100005];void divide(){ int i,j,k,t1,t2; N=(n<<1); tot=(N-1)/base+1; for(i=1;i<=tot;i++){ int pure=0,sum=0; for(j=i;j<=tot;j++){ int lim=j*base; lim=min(lim,N); for(k=(j-1)*base+1;k<=lim;k++){ t1=a[k]; t2=++cnt[a[k]]; if(t2>sum||(t2==sum&&a[k]<pure)){ sum=cnt[a[k]]; pure=a[k]; } } block[i][j]=node(pure,sum); if(i==1){ for(k=1;k<=m;k++){ all[j][k]=cnt[k]; } } } for(j=1;j<=m;j++)cnt[j]=0; }}int go_up(int x,int step){ int i; for(i=S;i>=0;i--){ if(step&(1<<i))x=p[x][i]; } return x;}void solve(int x){ //cout<<"solve:"<<x<<endl; int l,r,i,j,k; if(x==root){ l=1; r=n; } else if(id[x]<=id[root]&&id[root]<=R[x]){ //cout<<"case1"<<endl; int temp=go_up(root,dep[root]-dep[x]-1); l=R[temp]+1; r=id[temp]-1+n; } else { //cout<<"case2"<<endl; l=id[x];r=R[x]; } int bl,br,tl,tr; bl=(l-2+base)/base+1; br=r/base; tl=(bl-1)*base+1; tr=br*base; //cout<<"l:"<<l<<" r:"<<r<<endl; //cout<<"block("<<bl<<","<<br<<")"<<endl; //cout<<"work["<<l<<","<<r<<"]"<<endl; int pure,sum,t1,t2; if(bl>br){ //cout<<"fuck"<<endl; pure=0;sum=0; for(i=l;i<=r;i++){ t1=++cnt[a[i]]; t2=a[i]; if(t1>sum||(t1==sum&&t2<pure)){ sum=t1;pure=t2; } } //cout<<"cnt[105]:"<<cnt[105]<<endl; for(i=l;i<=r;i++)cnt[a[i]]=0; } else { pure=block[bl][br].Purity; sum=block[bl][br].sum; for(i=l;i<tl;i++){ t1=++cnt[a[i]]+all[br][a[i]]-all[bl-1][a[i]]; t2=a[i]; if(t1>sum||(t1==sum&&t2<pure)){ sum=t1;pure=t2; } } for(i=tr+1;i<=r;i++){ t1=++cnt[a[i]]+all[br][a[i]]-all[bl-1][a[i]]; t2=a[i]; if(t1>sum||(t1==sum&&t2<pure)){ sum=t1;pure=t2; } } for(i=l;i<tl;i++)cnt[a[i]]=0; for(i=tr+1;i<=r;i++)cnt[a[i]]=0; }新聞熱點
疑難解答
