前言

第一篇模擬賽題思路總結(jié)

題目相關(guān)

題目鏈接

題目大意

給定一個(gè)長度為$n$序列，每一個(gè)位置$i$都有一種顏色$a_i$
現(xiàn)在有$m$次操作，操作分兩種：
第一種操作，將所有顏色$x$都替換成$y$
第二種操作，詢問所有滿足兩個(gè)點(diǎn)的顏色分別為$x$和$y$的點(diǎn)對(duì)的最小距離值
強(qiáng)制在線

數(shù)據(jù)范圍

$n,m,a_i,x,y\le 200000$

題解

暴力分塊…
按照出現(xiàn)次數(shù)進(jìn)行分塊
我們來列舉一下要維護(hù)的信息：
顏色數(shù)組
對(duì)于所有顏色都維護(hù)出現(xiàn)位置的有序數(shù)組（我們發(fā)現(xiàn)輸入后處理這個(gè)信息復(fù)雜度是$\Theta (n)$的，可以使用vector）
對(duì)于出現(xiàn)次數(shù)$\ge \sqrt{n}$的顏色，額外維護(hù)其到其它所有顏色的答案(輸入后直接把整個(gè)序列掃一遍即可，我們發(fā)現(xiàn)滿足條件的顏色只有$\Theta (\sqrt{n})$種，總復(fù)雜度$\Theta (n\sqrt{n})$，空間復(fù)雜度同）。為了方便表示，設(shè)ans[i][j]代表當(dāng)前$i$顏色是L顏色，其與$j$顏色的答案
為了方便描述，我們稱出現(xiàn)次數(shù)$\ge \sqrt{n}$的顏色為L顏色，稱出現(xiàn)次數(shù)$\le \sqrt{n}$的顏色為S顏色

第一種操作

• L顏色&L顏色
  歸并維護(hù)有序數(shù)組，我們發(fā)現(xiàn)這種情況最多進(jìn)行$\sqrt{n}$次，所以這部分的復(fù)雜度為$\Theta (n\sqrt{n})$
  $\Theta (n)$維護(hù)顏色數(shù)組，總復(fù)雜度$\Theta (n\sqrt{n})$
  到其它所有顏色的答案也$\Theta (n)$維護(hù)，總復(fù)雜度$\Theta (n\sqrt{n})$
• S顏色&S顏色（注意，合并完后如果出現(xiàn)次數(shù)大于$\sqrt{n}$，需要將S顏色轉(zhuǎn)化成L顏色，容易發(fā)現(xiàn)這里最多出現(xiàn)$\sqrt{n}$次，所以總復(fù)雜度$\Theta (n\sqrt{n})$）
  歸并維護(hù)有序數(shù)組，復(fù)雜度$\Theta (\sqrt{n})$，總復(fù)雜度為$\Theta (m\sqrt{n})$
  $\Theta (\sqrt{n})$暴力維護(hù)顏色數(shù)組，總復(fù)雜度$\Theta (m\sqrt{n})$
• S顏色&L顏色
  S顏色并入L顏色與L顏色并入S顏色的本質(zhì)是一樣的，唯一不同的在于L顏色并入S顏色后顏色數(shù)組中需要更新的數(shù)據(jù)不同
  我們發(fā)現(xiàn)，L顏色$x$并入S顏色$y$,可以反向并入（即$y$并入$x$），并重新記下編號(hào)
  我們發(fā)現(xiàn)答案數(shù)組并不好維護(hù)，所以我們可以開一個(gè)緩沖區(qū)，記錄后面加入的零散的該顏色的位置（若緩沖區(qū)大小大于等于$\sqrt{n}$就直接用緩沖區(qū)更新，復(fù)雜度是$\Theta (n\sqrt{n})$的）
  更新緩沖區(qū)數(shù)組的復(fù)雜度是$\Theta (m\sqrt{n})$的

注意：任意顏色合并完畢后需要更新$\sqrt{n}$個(gè)L顏色中對(duì)應(yīng)的值

第二種操作

• L顏色&L顏色
  我們發(fā)現(xiàn)，答案數(shù)組維護(hù)的是L顏色的非緩沖區(qū)內(nèi)位置與別的顏色之間的答案，那么我們也就只需要將min(ans[x][y],ans[y][x])的值min上緩沖區(qū)之間的答案，復(fù)雜度$\Theta (\sqrt{n})$
• L顏色&S顏色
  將ans[x][y]min上緩沖區(qū)的答案，復(fù)雜度$\Theta (\sqrt{n})$
• S顏色&S顏色
  一次歸并即可

代碼

貼上AC代碼

#include<cstdio> #include<cctype> #include<cstring> #include<cstdlib> #include<algorithm> #include<vector> #include<cmath> namespace fast_IO {const int IN_LEN=10000000,OUT_LEN=10000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);} } using namespace fast_IO; #define getchar() getchar_() #define putchar(x) putchar_((x)) #define rg register typedef long long LL; template <typename T> inline T max(const T a,const T b){return a>b?a:b;} template <typename T> inline T min(const T a,const T b){return a<b?a:b;} template <typename T> inline void mind(T&a,const T b){a=a<b?a:b;} template <typename T> inline void maxd(T&a,const T b){a=a>b?a:b;} template <typename T> inline T abs(const T a){return a>0?a:-a;} template <typename T> inline void swap(T&a,T&b){T c=a;a=b;b=c;} template <typename T> inline T gcd(const T a,const T b){if(!b)return a;return gcd(b,a%b);} template <typename T> inline T lcm(const T a,const T b){return a/gcd(a,b)*b;} template <typename T> inline T square(const T x){return x*x;}; template <typename T> inline void read(T&x) {char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x; } template <typename T> inline void printe(const T x) {if(x>=10)printe(x/10);putchar(x%10+'0'); } template <typename T> inline void print(const T x) {if(x<0)putchar('-'),printe(-x);else printe(x); } const int INF=998244353; unsigned int PART; int n,m,col[200001]; int lsh[200001],tot,lastans; std::vector<int>p[200001],h[200001],ans[200001]; std::vector<int>::iterator Posu,Posv; void add(std::vector<int>&w,std::vector<int>&v) {std::vector<int>u;u.clear();for(unsigned int i=0;i<w.size();i++)u.push_back(w[i]);w.clear();Posu=u.begin(),Posv=v.begin();while(Posu!=u.end()&&Posv!=v.end())if((*Posu)<(*Posv))w.push_back(*Posu),Posu++;else w.push_back(*Posv),Posv++;while(Posu!=u.end())w.push_back(*Posu),Posu++;while(Posv!=v.end())w.push_back(*Posv),Posv++;v.clear(); } int calc(std::vector<int>&u,std::vector<int>&v) {int ans=INF,lasu=-INF,lasv=-INF;Posu=u.begin(),Posv=v.begin();while(Posu!=u.end()&&Posv!=v.end())if((*Posu)<(*Posv))lasu=*Posu,Posu++,mind(ans,lasu-lasv);else lasv=*Posv,Posv++,mind(ans,lasv-lasu);while(Posu!=u.end())lasu=*Posu,Posu++,mind(ans,lasu-lasv);while(Posv!=v.end())lasv=*Posv,Posv++,mind(ans,lasv-lasu);return ans; } int bak[200001]; bool isL[200001]; void L_color_update(const int u) {std::vector<int>*U=&ans[u];for(rg int i=1;i<=tot;i++)(*U)[i]=INF;int close=INF;for(rg int i=1;i<=n;i++,close++)if(col[i]==u)close=0;else mind((*U)[col[i]],close);close=INF;for(rg int i=n;i>=1;i--,close++)if(col[i]==u)close=0;else mind((*U)[col[i]],close); } bool is[200001]; void upd(std::vector<int>&u) {for(Posu=u.begin();Posu!=u.end();Posu++)is[*Posu]=1;u.clear(); } int Lstack[200001],Ltop; void push(const int x){Lstack[++Ltop]=x,ans[x].resize(200001),isL[x]=1;} void pop(const int x) {ans[x].clear(),isL[x]=0;for(rg int i=1;i<=Ltop;i++)if(Lstack[i]==x){Ltop--;for(rg int j=i;j<=Ltop;j++)Lstack[j]=Lstack[j+1];return;} } int main() {read(n),read(m),PART=sqrt(n);for(rg int i=1;i<=n;i++){read(col[i]);if(!lsh[col[i]])lsh[col[i]]=++tot;col[i]=lsh[col[i]];p[col[i]].push_back(i);}for(rg int i=1;i<=tot;i++)if(p[i].size()>=PART){push(i);L_color_update(i);}for(rg int i=1;i<=m;i++){int opt,x,y;read(opt),read(x),read(y);x^=lastans,y^=lastans;if(opt==1){const int X=lsh[x],Y=lsh[y];if(!X||x==y)continue;if(!Y){lsh[x]=0;lsh[y]=X;continue;}if(isL[X]){if(isL[Y]){upd(p[X]),upd(p[Y]),upd(h[X]),upd(h[Y]);for(rg int j=1;j<=n;j++)if(is[j])p[Y].push_back(j),is[j]=0,col[j]=Y;L_color_update(Y);lsh[x]=0,pop(X);for(rg int j=1;j<=Ltop;j++){const int v=Lstack[j];ans[v][Y]=ans[Y][v];}}else{for(Posv=p[Y].begin();Posv!=p[Y].end();Posv++)col[*Posv]=X;add(h[X],p[Y]);for(rg int j=1;j<=Ltop;j++){const int v=Lstack[j];mind(ans[v][X],ans[v][Y]),ans[v][Y]=INF;}if(h[X].size()>=PART){upd(p[X]),upd(h[X]);for(rg int j=1;j<=n;j++)if(is[j])p[X].push_back(j),is[j]=0;L_color_update(X);}lsh[x]=0,lsh[y]=X;}}else{if(isL[Y]){for(Posv=p[X].begin();Posv!=p[X].end();Posv++)col[*Posv]=Y;add(h[Y],p[X]);for(rg int j=1;j<=Ltop;j++){const int v=Lstack[j];mind(ans[v][Y],ans[v][X]),ans[v][X]=INF;}if(h[Y].size()>=PART){upd(p[Y]),upd(h[Y]);for(rg int j=1;j<=n;j++)if(is[j])p[Y].push_back(j),is[j]=0;L_color_update(Y);}lsh[x]=0;}else{for(Posv=p[X].begin();Posv!=p[X].end();Posv++)col[*Posv]=Y;add(p[Y],p[X]);for(rg int j=1;j<=Ltop;j++){const int v=Lstack[j];mind(ans[v][Y],ans[v][X]),ans[v][X]=INF;}if(p[Y].size()>=PART){push(Y);upd(p[Y]);for(rg int j=1;j<=n;j++)if(is[j])p[Y].push_back(j),is[j]=0;L_color_update(Y);for(rg int j=1;j<=Ltop;j++){const int v=Lstack[j];ans[v][Y]=ans[Y][v];}}lsh[x]=0;}}}else{if(!lsh[x]||!lsh[y])putchar('y'),putchar('y'),putchar('b'),putchar(' '),putchar('i'),putchar('s'),putchar(' '),putchar('o'),putchar('u'),putchar('r'),putchar(' '),putchar('r'),putchar('e'),putchar('d'),putchar(' '),putchar('s'),putchar('u'),putchar('n'),putchar(' '),putchar('a'),putchar('n'),putchar('d'),putchar(' '),putchar('z'),putchar('s'),putchar('y'),putchar(' '),putchar('i'),putchar('s'),putchar(' '),putchar('o'),putchar('u'),putchar('r'),putchar(' '),putchar('b'),putchar('l'),putchar('u'),putchar('e'),putchar(' '),putchar('m'),putchar('o'),putchar('o'),putchar('n'),lastans=0;else{const int X=lsh[x],Y=lsh[y];if(isL[X]){if(isL[Y])print(lastans=min(min(ans[X][Y],ans[Y][X]),calc(h[X],h[Y])));else print(lastans=min(ans[X][Y],calc(h[X],p[Y])));}else{if(isL[Y])print(lastans=min(ans[Y][X],calc(p[X],h[Y])));else print(lastans=calc(p[X],p[Y]));}}putchar('\n');}}return flush(),0; }

總結(jié)

分塊好題，很妙的思路

總結(jié)

以上是生活随笔為你收集整理的模拟赛-20190114-新魔法(distance)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。