MinhNGUYEN2k4

Untitled

Sep 15th, 2021
746
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. //#define int long long
  3. #define double long double
  4. #define Task "MAXLEN"
  5. #define READFILE freopen(Task".inp", "r", stdin)
  6. #define WRITEFILE freopen(Task".out", "w", stdout)
  7. #define double long double
  8. #define oo 0x3f3f3f3f3f
  9. #define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  10. #define mp make_pair
  11. #define pb push_back
  12. #define X first
  13. #define Y second
  14. #define watch(x) cout << (#x) << " = " << x << endl
  15. #define debug(x) cout << (#x) << " = " << x << endl
  16. #define all(x) x.begin(), x.end()
  17. #define sz(x) x.size()
  18. #define endl '\n'
  19. #define max3(a,b,c) max(max(a, b), c)
  20. #define max4(a,b,c,d) max(max(a, b), max(c, d))
  21. #define min4(a,b,c,d) min(min(a, b), min(c, d))
  22. #define debug4(a,b,c,d) watch(a);watch(b);watch(c);watch(d)
  23. #define ever (;true;)
  24. #define maxn 505
  25.  
  26. #define PI 3.14159265
  27.  
  28. using namespace std;
  29.  
  30. typedef pair < int, int > ii;
  31. typedef pair < int, ii > iii;
  32. typedef pair < ii, ii > iiii;
  33. typedef vector < int > vi;
  34. typedef vector < ii > vii;
  35. typedef vector < vi > vvi;
  36. typedef vector < iii > viii;
  37. typedef vector < vii > vvii;
  38. typedef vector < iiii > viiii;
  39. typedef vector < vvi > vvvi;
  40.  
  41. const int N = 1e5 + 5;
  42. const int Blocksize = 316;
  43.  
  44. int n, q;
  45. int a[N];
  46.  
  47. int b[Blocksize + 5][N];
  48. int c[Blocksize + 5][N];
  49.  
  50. struct Nho{
  51.     int nho[N];
  52.     int TimeUpdate[N];
  53.     int Time = 0;
  54.     Nho(){
  55.         memset(TimeUpdate, 0, sizeof(TimeUpdate));
  56.         Time = 1;
  57.     }
  58.  
  59.     void set(int i, int val){
  60.         TimeUpdate[i] = Time;
  61.         nho[i] = val;
  62.     }
  63.  
  64.     int Get(int i){
  65.         if (TimeUpdate[i] != Time) return 0;
  66.         return nho[i];
  67.     }
  68.  
  69.     void reset(){
  70.         ++Time;
  71.     }
  72.  
  73. }nho;
  74.  
  75. void init(){
  76.     FAST;
  77.     #ifndef ONLINE_JUDGE
  78.     READFILE;
  79.     WRITEFILE;
  80.     #endif // ONLINE_JUDGE
  81.     scanf("%d%d", &n, &q);
  82.     for (int i = 1; i <= n; ++i){
  83.         scanf("%d", a + i);
  84.     }
  85.     vi val(a+1, a+1+n);
  86.     sort(all(val));
  87.     for (int i = 1; i <= n; ++i){
  88.         a[i] = lower_bound(all(val), a[i]) - val.begin();
  89.     }
  90. }
  91.  
  92. void pp(){
  93.     for (int k = 0; (k+1) * Blocksize <= n; ++k){
  94.         nho.reset();
  95.         for (int i = k*Blocksize + 1; i <= n; ++i){
  96.             int j = nho.Get(a[i]);
  97.             b[k][i] = b[k][i-1];
  98.             if (j) b[k][i] = max(b[k][i], i - j);
  99.             else nho.set(a[i], i);
  100.         }
  101.     }
  102.     for (int k = 0; (k+1) * Blocksize <= n; ++k){
  103.         nho.reset();
  104.         for (int i = (k+1) * Blocksize; i >= 1; --i){
  105.             int j = nho.Get(a[i]);
  106.             c[k][i] = c[k][i+1];
  107.             if (j) c[k][i] = max(c[k][i], j - i);
  108.             else nho.set(a[i], i);
  109.         }
  110.     }
  111. }
  112.  
  113. void Solve(){
  114.     while (q--){
  115.         int l, r;
  116.         scanf("%d%d", &l, &r);
  117.         int u = (l - 1) / Blocksize;
  118.         int v = (r - 1) / Blocksize;
  119.         if (v - u <= 1){
  120.             nho.reset();
  121.             int ans = 0;
  122.             for (int i = l; i <= r; ++i){
  123.                 int j = nho.Get(a[i]);
  124.                 if (j) ans = max(ans, i - j);
  125.                 else nho.set(a[i], i);
  126.             }
  127.             cout << ans << endl;
  128.         }
  129.         else{
  130.             int ans = max(b[u+1][r], c[v-1][l]);
  131.             nho.reset();
  132.             for (int i = l; i <= (u+1) * Blocksize; ++i){
  133.                 int j = nho.Get(a[i]);
  134.                 if (j) ans = max(ans, i - j);
  135.                 else nho.set(a[i], i);
  136.             }
  137.             for (int i = v*Blocksize + 1; i <= r; ++i){
  138.                 int j = nho.Get(a[i]);
  139.                 if (j) ans = max(ans, i - j);
  140.                 else nho.set(a[i], i);
  141.             }
  142.             cout << ans << endl;
  143.         }
  144.     }
  145. }
  146.  
  147. signed main(){
  148.     init();
  149.     pp();
  150.     Solve();
  151.     return 0;
  152. }
RAW Paste Data