SHARE
TWEET

Untitled

a guest Jan 21st, 2016 836 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define forn(i, n) for (int i = 0; i < int(n); i++)
  4. #define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
  5. #define fore(i, l, r) for (int i = int(l); i < int(r); i++)
  6. #define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
  7. #define all(a) (a).begin(), (a).end()
  8. #define sz(a) int((a).size())
  9. #define pb(a) push_back(a)
  10. #define mp(x, y) make_pair((x), (y))
  11. #define x first
  12. #define y second
  13.  
  14. using namespace std;
  15.  
  16. typedef long long li;
  17. typedef long double ld;
  18. typedef pair<int, int> pt;
  19.  
  20. template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
  21. template<typename X> inline X sqr(const X& a) { return a * a; }
  22.  
  23. const int INF = int(1e9);
  24. const li INF64 = li(1e18);
  25. const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
  26.  
  27. const int N = 100100, LOGN = 20;
  28.  
  29. int n, m;
  30. int a[N];
  31. pair<pt, int> q[N];
  32.  
  33. inline bool read() {
  34.     if (!(cin >> n >> m)) return false;
  35.     forn(i, n) assert(scanf("%d", &a[i]) == 1);
  36.     forn(i, m) {
  37.         assert(scanf("%d%d", &q[i].x.x, &q[i].x.y) == 2);
  38.         q[i].x.x--;
  39.         q[i].y = i;
  40.     }
  41.     return true;
  42. }
  43.  
  44. inline int getXor(int a) {
  45.     switch (a % 4) {
  46.         case 0: return a;
  47.         case 1: return 1;
  48.         case 2: return a + 1;
  49.         case 3: return 0;
  50.     }
  51.     throw;
  52. }
  53.  
  54. struct node {
  55.     int nt[2];
  56.     int maxv;
  57.     node() {
  58.         nt[0] = nt[1] = -1;
  59.         maxv = INT_MIN;
  60.     }
  61. };
  62.  
  63. int szt[2], root[2];
  64. node t[2][N * LOGN];
  65.  
  66. inline int newNode(int i) {
  67.     t[i][szt[i]] = node();
  68.     return szt[i]++;
  69. }
  70.  
  71. inline void clear() {
  72.     forn(i, 2) {
  73.         szt[i] = 0;
  74.         root[i] = newNode(i);
  75.     }
  76. }
  77.  
  78. inline void lift(int ti, int v) {
  79.     node *t = ::t[ti];
  80.     t[v].maxv = INT_MIN;
  81.     forn(i, 2) {
  82.         int nv = t[v].nt[i];
  83.         if (nv != -1) {
  84.             t[v].maxv = max(t[v].maxv, t[nv].maxv);
  85.             //cerr << "vvv=" << t[nv].maxv << endl;
  86.         }
  87.     }
  88.     //cerr << t[v].maxv << endl;
  89. }
  90.  
  91. int calc(int ti, int x, int minv) {
  92.     int v = root[ti];
  93.     node *t = ::t[ti];
  94.  
  95.     if (minv > t[v].maxv) return 0;
  96.     int ans = 0;
  97.     ford(i, LOGN) {
  98.         int d = (x >> i) & 1;
  99.         bool f = false;
  100.         ford(jj, 2) {
  101.             int j = jj ^ d;
  102.             int vv = t[v].nt[j];
  103.             if (vv != -1 && minv <= t[vv].maxv) {
  104.                 v = t[v].nt[j];
  105.                 f = true;
  106.                 if (jj) ans |= 1 << i;
  107.                 break;
  108.             }
  109.         }
  110.         assert(f && minv <= t[v].maxv);
  111.     }
  112.     return ans;
  113. }
  114.  
  115. void add(int ti, int x, int curv) {
  116.     int v = root[ti];
  117.     node *t = ::t[ti];
  118.  
  119.     static int szvs, vs[LOGN];
  120.     szvs = 0;
  121.  
  122.     ford(i, LOGN) {
  123.         vs[szvs++] = v;
  124.         int d = (x >> i) & 1;
  125.         int& nt = t[v].nt[d];
  126.         if (nt == -1) nt = newNode(ti);
  127.         assert(nt != -1);
  128.         v = nt;
  129.     }
  130.  
  131.     t[v].maxv = max(t[v].maxv, curv);
  132.     ford(i, szvs) lift(ti, vs[i]);
  133. }
  134.  
  135. int ans[N];
  136.  
  137. void solve(int l, int r, int rx) {
  138.     sort(q + l, q + r, [](const pair<pt, int>& a, const pair<pt, int>& b) { return a.x.y < b.x.y; });
  139.  
  140.     clear();
  141.     int px = rx;
  142.     int cmax = 0;
  143.     fore(i, l, r) {
  144.         int lf = q[i].x.x, rg = q[i].x.y, id = q[i].y;
  145.  
  146.         while (px < rg) {
  147.             int x = a[px++];
  148.             add(0, getXor(x), x);
  149.             cmax = max(cmax, calc(0, getXor(x - 1), x));
  150.             add(1, getXor(x - 1), -x);
  151.             cmax = max(cmax, calc(1, getXor(x), -x));
  152.         }
  153.  
  154.         int vmax = cmax;
  155.         fore(j, lf, min(rg, rx)) {
  156.             int x = a[j];
  157.             vmax = max(vmax, calc(0, getXor(x - 1), x));
  158.             vmax = max(vmax, calc(1, getXor(x), -x));
  159.         }
  160.  
  161.         ans[id] = max(ans[id], vmax);
  162.     }
  163.  
  164.     fore(i, l, r) {
  165.         int lf = q[i].x.x, rg = min(q[i].x.y, rx), id = q[i].y;
  166.  
  167.         clear();
  168.         int cmax = 0;
  169.         fore(j, lf, rg) {
  170.             int x = a[j];
  171.             add(0, getXor(x), x);
  172.             cmax = max(cmax, calc(0, getXor(x - 1), x));
  173.             add(1, getXor(x - 1), -x);
  174.             cmax = max(cmax, calc(1, getXor(x), -x));
  175.         }
  176.  
  177.         ans[id] = max(ans[id], cmax);
  178.     }
  179. }
  180.  
  181. inline void solve() {
  182.     sort(q, q + m);
  183.     forn(i, m) ans[i] = 0;
  184.  
  185.     int i = 0, j = 0;
  186.     const int S = 800;
  187.     for (int lx = 0; lx < n; lx += S) {
  188.         int rx = min(n, lx + S);
  189.         while (j < m) {
  190.             assert(lx <= q[j].x.x);
  191.             if (q[j].x.x >= rx) break;
  192.             j++;
  193.         }
  194.         solve(i, j, rx);
  195.         i = j;
  196.         cerr << "lx=" << lx << endl;
  197.     }
  198.  
  199.     forn(i, m) printf("%d\n", ans[i]);
  200. }
  201.  
  202. int main() {
  203. #ifdef SU1
  204.     assert(freopen("input.txt", "rt", stdin));
  205.     assert(freopen("output.txt", "wt", stdout));
  206. #endif
  207.    
  208.     cout << setprecision(10) << fixed;
  209.     cerr << setprecision(5) << fixed;
  210.  
  211.     while (read()) {
  212.         solve();
  213.         break;
  214.     }
  215.  
  216.     cerr << "TIME=" << clock() / ld(CLOCKS_PER_SEC) << endl;
  217.    
  218.     return 0;
  219. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top