fork download 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <iomanip>
  6. #include <stdio.h>
  7.  
  8. #include <set>
  9. #include <unordered_set>
  10. #include <bitset>
  11. #include <map>
  12. #include <unordered_map>
  13. #include <queue>
  14. #include <deque>
  15. #include <vector>
  16. #include <ext/pb_ds/assoc_container.hpp>
  17. #include <ext/pb_ds/tree_policy.hpp>
  18.  
  19. using namespace std;
  20. using namespace __gnu_pbds;
  21.  
  22. #define ll long long
  23. #define ld long double
  24. #define fi first
  25. #define se second
  26. #define pb push_back
  27. #define mp make_pair
  28. #define ii pair<int,int>
  29. #define pli pair<ll,int>
  30. #define pll pair<ll,ll>
  31. #define pil pair<int,ll>
  32. #define plii pair<ll,pair<int,int>>
  33. #define heapmax(type) priorpy_queue<type>
  34. #define heapmin(type) priorpy_queue<type,vector<type>,greater<type>>
  35. #define ordered_multiset  tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_starttistics_node_update>
  36. #define ordered_set       tree<int, null_type, less<int>, rb_tree_tag, tree_order_starttistics_node_update>
  37. #define FASTIO ios::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
  38. #define sz(x) (int)x.size()
  39. #define all(x) (x).begin(),(x).end()
  40. #define getbp(mask,i) ((mask >> i) & 1)
  41.  
  42. template<typename T> bool maximize(const T &res2, const T &val) { if (res2 <  val) { res2 = val; return true; } return false; }
  43. template<typename T> bool minimize(const T &res2, const T &val) { if (res2 >  val) { res2 = val; return true; } return false; }
  44. template<typename T> ll rv_n(T x){
  45.     ll res2 = 0;
  46.     while (x > 0) res2 = res2*10 + x % 10 , x/=10;
  47.     return res2;
  48. }
  49. const ll mod = 1e9 + 7;
  50. const ld PI = acos(-1);
  51. const int N = 1e6 + 100;
  52. const int N_Trie = 1e5;
  53. const int N_ST = 2e5 + 10;
  54. const int N_BIT = 2e5 + 10;
  55. const int LIM = 1e7; // N_Prime
  56. const int N_MST = 1e5; // N of Merge Sort Tree
  57. const int N_Hash = 2e6 + 10;
  58.  
  59. // sort(all(V));
  60. // V.res2ize(unique(all(V)) - V.begin());*/
  61.  
  62. struct Trie_Number{
  63.     struct DT{
  64.         ii c[2];
  65.     };
  66.     DT trie[32*N_Trie];
  67.     bool vve[33];
  68.     int pw[32] , am = 0;
  69.     void Built_PW(){
  70.         pw[0] = 1;
  71.         for (int i = 1; i < 32; i++) pw[i] = pw[i - 1] * 2;
  72.     }
  73.     void _res2et(){
  74.         memset(vve,0,sizeof(vve));
  75.         memset(trie,0,sizeof(trie));
  76.     }
  77.     void _change(int x){
  78.         int p = 0;
  79.         while (x > 0){
  80.             vve[++p] = x % 2;
  81.             x /= 2;
  82.         }
  83.         while (p < 32) vve[++p] = 0;
  84.     }
  85.     void _add(int x){
  86.         _change(x);
  87.         int node = 0;
  88.         for (int i = 32; i >= 1; i--){
  89.             int w = vve[i];
  90.             if (!trie[node].c[w].fi) trie[node].c[w].fi = ++am;
  91.             trie[node].c[w].se++;
  92.             if (i > 1) node = trie[node].c[w].fi;
  93.         }
  94.     }
  95.     void _delete(int x){
  96.         _change(x);
  97.         int node = 0;
  98.         for (int i = 32; i >= 1; i--){
  99.             int w = vve[i];
  100.             if (!trie[node].c[w].fi){
  101.                 return;
  102.             }
  103.             if (trie[node].c[w].se == 0){
  104.                 return;
  105.             }
  106.             if (i > 1) node = trie[node].c[w].fi;
  107.         }
  108.         node = 0;
  109.         for (int i = 32; i >= 1; i--){
  110.             int w = vve[i];
  111.             // if (trie[node].c[w].se > 0)
  112.                 trie[node].c[w].se--;
  113.             if (i > 1) node = trie[node].c[w].fi;
  114.         }
  115.     }
  116.     int _get(int k){
  117.         int node = 0 , res2 = 0;
  118.         for (int i = 32; i >= 1; i--){
  119.             if (k <= trie[node].c[0].se){
  120.                 if (!trie[node].c[0].se) return -1;
  121.                 node = trie[node].c[0].fi;
  122.             }
  123.             else{
  124.                 if (!trie[node].c[1].se) return -1;
  125.                 k = k - trie[node].c[0].se;
  126.                 node = trie[node].c[1].fi;
  127.                 res2 = res2 + pw[i - 1];
  128.             }
  129.         }
  130.         return res2;
  131.     }
  132. };
  133. ll gcd(ll a, ll b) {
  134.   if (b == 0) return a;
  135.   else return gcd(b, a % b);
  136. }
  137. ll snt[LIM + 2];
  138. void Sieve() {
  139.   for(ll i = 1; i <= LIM; i++) snt[i] = 0;
  140.   for(ll i = 1; i <= LIM; i++) {
  141.     for(ll j = i; j <= LIM; j += i) {
  142.       snt[j] += i;
  143.     }
  144.   }
  145. }
  146. bool ktsnt(ll n) {
  147.   if (n <= 1) return false;
  148.   if (n <= 3) return true;
  149.   if (n % 2 == 0 || n % 3 == 0) return false;
  150.   for (int i = 5; i * i <= n; i += 6) {
  151.     if (n % i == 0 || n % (i + 2) == 0){
  152.       return false;
  153.     }
  154.   }
  155.   return true;
  156. }
  157. ll mul(ll a,ll b,ll c){ // O(log(min(a,b)))
  158.     if (a < b) swap(a,b);
  159.     ll res2 = 0;
  160.     a = a % c;
  161.     for (; b > 0; b >>= 1 , a = (a + a) % c)
  162.         if (b & 1) res2 = (res2 + a) % c;
  163.     return res2;
  164. }
  165. ll power(ll a,ll b,ll c){ // O(log(b))
  166.     ll res2 = 1;
  167.     a = a % c;
  168.     for (; b > 0; b >>= 1 , a = a * a % c)
  169.         if (b & 1) res2 = res2 * a % c;
  170.     return res2;
  171. }
  172. ll power_mul(ll a,ll b,ll c){ // O(log(b)^2)
  173.     ll res2 = 1;
  174.     a = a % c;
  175.     for (; b > 0; b >>= 1 , a = mul(a,a,c))
  176.         if (b & 1) res2 = mul(res2,a,c);
  177.     return res2;
  178. }
  179. void file(const string FILE){
  180.     if (fopen((FILE + ".INP").c_str(),"r")){
  181.         freopen((FILE + ".INP").c_str(), "r", stdin);
  182.         freopen((FILE + ".OUT").c_str(), "w", stdout);
  183.     }
  184. }
  185. void solve(){
  186.   int n, q;
  187.   map<int, set<int>> mp;
  188.   vector<int> a(N), psum(N);
  189.   cin >> n >> q;
  190.   for(int i = 1; i <= n; i++){
  191.     cin >> a[i];
  192.     psum[i] = psum[i - 1] ^ a[i];
  193.   }
  194.   for(int i = 0; i <= n; i++){
  195.     mp[psum[i]].insert(i);
  196.   }
  197.   while (q--){
  198.     int l, r;
  199.     cin >> l >> r;
  200.     if (psum[r] == psum[l - 1]){
  201.       cout << "YES\n";
  202.     }
  203.     else {
  204.       auto it = mp[psum[l - 1]].upper_bound(r); it--;
  205.       int u = *(it);
  206.       it = mp[psum[r]].lower_bound(l);
  207.       int v = *(it);
  208.       if (u <= r && v <= r - 1 && v + 1 <= u && l <= v){
  209.         cout << "YES\n";
  210.       }
  211.       else cout << "NO\n";
  212.     }
  213.   }
  214. }
  215. int main(){
  216.   FASTIO;
  217.   int t = 1;
  218.   cin >> t;
  219.   while(t--){
  220.     solve();
  221.   }
  222.   return 0;
  223. }
  224.  
Success #stdin #stdout 0.02s 11432KB
comments (?)
stdin 
4
5 5
1 1 2 3 0
1 5
2 4
3 5
1 3
3 4
5 5
1 2 3 4 5
1 5
2 4
3 5
1 3
2 3
7 4
12 9 10 9 10 11 9
1 5
1 7
2 6
2 7
11 4
0 0 1 0 0 1 0 1 1 0 1
1 2
2 5
6 9
7 11
stdout 
YES
YES
NO
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
YES
NO
YES
YES
https://ideone.com/3iLklV
language:
C++14 (gcc 8.3)
created:
14 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!