MinhNGUYEN2k4

Untitled

Sep 20th, 2021
711
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int N = 1e5+5;
  5. const int ssize=316;
  6.  
  7. int n, m;
  8. int a[N];
  9. int b[ssize+5][N];
  10. int c[ssize+5][N];
  11.  
  12. int MAX(int x, int y){
  13.     if (x>y) return x;
  14.     return y;
  15. }
  16.  
  17. struct NHO{
  18.     int nho[N];
  19.     long long tim[N];
  20.     long long T=0;
  21.     NHO(){
  22.         memset(tim, 0, sizeof tim);
  23.         T=1;
  24.     }
  25.     void reset(){T++;}
  26.     int get(int x){
  27.         if (tim[x]!=T) return 0;
  28.         return nho[x];
  29.     }
  30.     void Set(int x, int val){
  31.         tim[x] = T;
  32.         nho[x] = val;
  33.     }
  34. };
  35. NHO nho;
  36.  
  37. int main()
  38. {
  39.     if (fopen("test.inp","r")) freopen("test.inp","r",stdin);
  40.     ios_base::sync_with_stdio(false);
  41.     cin.tie(0);cout.tie(0);
  42.     cin >> n >> m;
  43.     for(int i=1; i<=n; i++) cin >> a[i];
  44.     vector<int> bb(a+1,a+1+n);
  45.     sort(bb.begin(),bb.end());
  46.     for(int i=1; i<=n; i++) a[i] = lower_bound(bb.begin(),bb.end(),a[i])-bb.begin();
  47.     for(int k=0; (k+1)*ssize<=n; k++){
  48.         nho.reset();
  49.         int u = k*ssize + 1;
  50.         for(int i=u; i<=n; i++){
  51.             int j = nho.get(a[i]);
  52.             if (j) b[k][i] = MAX(b[k][i-1],i-j);
  53.             else nho.Set(a[i],i), b[k][i] = b[k][i-1];
  54.         }
  55.     }
  56.     for(int k=0; k<=ssize; k++){
  57.         nho.reset();
  58.         int u = min(n,(k+1)*ssize);
  59.         for(int i=u; i>=1; i--){
  60.             int j = nho.get(a[i]);
  61.             if (j) c[k][i] = MAX(c[k][i+1],j-i);
  62.             else nho.Set(a[i],i), c[k][i] = c[k][i+1];
  63.         }
  64.     }
  65.     while (m--){
  66.         int l, r;
  67.         cin >> l >> r;
  68.         int u = (l-1)/ssize;
  69.         int v = (r-1)/ssize;
  70.         int res=0;
  71.         if (v-u<=1){
  72.             nho.reset();
  73.             for(int i=l; i<=r; i++){
  74.                 int j = nho.get(a[i]);
  75.                 if (j) res = MAX(res,i-j);
  76.                 else nho.Set(a[i],i);
  77.             }
  78.             cout << res << '\n';
  79.         }
  80.         else{
  81.             res = MAX(b[u+1][r],c[v-1][l]);
  82.             nho.reset();
  83.             for(int i=l; i<=(u+1)*ssize; i++){
  84.                 int j = nho.get(a[i]);
  85.                 if (j) res = MAX(res,i-j);
  86.                 else nho.Set(a[i],i);
  87.             }
  88.             for(int i=v*ssize+1; i<=r; i++){
  89.                 int j = nho.get(a[i]);
  90.                 if (j) res = MAX(res,i-j);
  91.                 else nho.Set(a[i],i);
  92.             }
  93.             cout << res << '\n';
  94.         }
  95.     }
  96.     return 0;
  97. }
  98.  
RAW Paste Data