제출 #399605

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
399605		cadmiumsky	XORanges (eJOI19_xoranges)	C++14	100 / 100	669 ms	20616 KiB

xoranges

#include <iostream>
#include <vector>
#define int unsigned long long 
using namespace std;

int polar[2]={0,(1LL<<32)-1};

int n;

int v[200001];

class AINT {
  vector<int> tree;
  int pol;
  public:
    void reset(int len,int polarity) {
      tree=vector<int>(4*len+1,0);
      pol=polarity;
    }
    void construct(int node=1, int cl=1, int cr=n) {
      if(cl==cr) {
        tree[node]=(v[cl-1]&(polar[pol^(cl&1)]));
      }
      else {
        int mid=(cl+cr)/2;
        construct(2*node,cl,mid);
        construct(2*node+1,mid+1,cr);
        tree[node]=(tree[2*node]^tree[2*node+1]);
      }
      return;
    }
    void update(const int poz,const int val, int node=1, int cl=1,int cr=n) {
      if(cl==cr) {
        tree[node]=(val&(polar[pol^(poz&1)]));
        return;
      }
      int mid=(cl+cr)/2;
      if(poz<=mid)
        update(poz,val,2*node,cl,mid);
      else 
        update(poz,val,2*node+1,mid+1,cr);
      tree[node]=(tree[2*node]^tree[2*node+1]);
      //cout << pol <<'\t'<< node <<' ' << cl <<' ' << cr <<' '<< tree[4] <<'\n';
    }
    int query(const int left,const int right, int node=1, int cl=1, int cr=n) {
      //cout << cl << ' '<< cr  <<' '<< node <<' ' << tree[node] <<'\n';
      if(left<=cl && cr<=right) {
        return tree[node];
      }
      int mid=(cl+cr)/2,ans=0;
      if(left<=mid)
        ans=query(left,right,2*node,cl,mid);
      if(mid<right)
        ans^=query(left,right,2*node+1,mid+1,cr);
      return ans;
    }
} pol1,pol0;

signed main() {
  int q;
  cin >> n >> q;
  for(int i=0; i<n; i++)
    cin >> v[i];
  pol1.reset(n,1);
  pol0.reset(n,0);
  pol1.construct();
  pol0.construct();
  for(int type,x,y,i=0; i<q; i++) {
    cin >> type >>x >> y;
    if(type==1) {
      pol1.update(x,y);
      pol0.update(x,y);
    }
    else {
      if(((x^y)&1)==0) {
        //cout << "MAATa\n";
        if(x&1)
          cout << pol0.query(x,y);
        else
          cout << pol1.query(x,y);
      }
      else
        cout << 0;
      cout << '\n';
    }
  }
  return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 25 / 25
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25