1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106
| #include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> using namespace std; inline const int Get_Int() { int num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } const int maxn=100005,maxb=sqrt(maxn)+5; int n,m,k,a[maxn],Belong[maxn],Left[maxn],Right[maxn],BCC=0,First[maxb][maxn],Last[maxb][maxn],cal[maxb][maxb],f[maxb][maxb],LMax[maxb][maxn],RMax[maxb][maxn]; vector<int>exist[maxb]; void build(int cnt,int L,int R) { for(int i=0; i<exist[cnt].size(); i++)First[cnt][exist[cnt][i]]=0x3f3f3f3f,Last[cnt][exist[cnt][i]]=0; exist[cnt].clear(); for(int i=L; i<=R; i++) { if(First[cnt][a[i]]==0x3f3f3f3f) { First[cnt][a[i]]=i; exist[cnt].push_back(a[i]); } Last[cnt][a[i]]=i; } } int main() { n=Get_Int(); m=Get_Int(); k=Get_Int(); for(int i=1; i<=n; i++)a[i]=Get_Int(); int size=sqrt(n); for(int i=1; i<=n; i++) { Belong[i]=(i-1)/size+1; if(!Left[Belong[i]])Left[Belong[i]]=i,BCC++; Right[Belong[i]]=i; } memset(First,0x3f,sizeof(First)); for(int i=1; i<=BCC; i++) for(int j=Left[i]; j<=Right[i]; j++) { if(First[i][a[j]]==0x3f3f3f3f) { First[i][a[j]]=j; exist[i].push_back(a[j]); } Last[i][a[j]]=j; } for(int x=1; x<=BCC; x++) for(int y=x; y<=BCC; y++) for(int i=0; i<exist[x].size(); i++) cal[x][y]=max(cal[x][y],Last[y][exist[x][i]]-First[x][exist[x][i]]); for(int len=1; len<=BCC; len++) for(int i=1; i+len-1<=BCC; i++) { int j=i+len-1; f[i][j]=max(max(f[i+1][j],f[i][j-1]),cal[i][j]); } for(int i=1; i<=BCC; i++) for(int j=1; j<=m; j++) LMax[i][j]=max(LMax[i-1][j],Last[i][j]); memset(RMax,0x3f,sizeof(RMax)); for(int i=BCC; i>=1; i--) for(int j=1; j<=m; j++) RMax[i][j]=min(RMax[i+1][j],First[i][j]); for(int i=1; i<=k; i++) { int x=Get_Int(),y=Get_Int(),cnt=BCC+1; int L=Belong[x],R=Belong[y],st=L,ed=R; if(L==R) { st=BCC+3; ed=0; L=R=cnt; build(cnt++,x,y); } else { if(x!=Left[Belong[x]]) { st=L+1; L=cnt; build(cnt++,x,Right[Belong[x]]); } if(y!=Right[Belong[y]]) { ed=R-1; R=cnt; build(cnt++,Left[Belong[y]],y); } } int ans=f[st][ed]; for(int i=0; i<exist[L].size(); i++) ans=max(ans,Last[R][exist[L][i]]-First[L][exist[L][i]]); if(R>BCC) for(int i=0; i<exist[R].size(); i++) ans=max(ans,Last[R][exist[R][i]]-RMax[st][exist[R][i]]); if(L>BCC) for(int i=0; i<exist[L].size(); i++) ans=max(ans,LMax[ed][exist[L][i]]-First[L][exist[L][i]]); printf("%d\n",ans); } return 0; }
|