Task: | Xor sum |
Sender: | minghao |
Submission time: | 2024-09-23 16:22:39 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.32 s | details |
Compiler report
input/code.cpp: In function 'void Test()': input/code.cpp:136:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result] 136 | freopen("temp\\in.txt", "r", stdin); | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~ input/code.cpp: In function 'int main()': input/code.cpp:142:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result] 142 | scanf("%d%d", &n, &q); | ~~~~~^~~~~~~~~~~~~~~~ input/code.cpp:147:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result] 147 | scanf("%d", &x); | ~~~~~^~~~~~~~~~ input/code.cpp:154:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result] 154 | scanf("%d%d", &a, &b); | ~~~~~^~~~~...
Code
#include<iostream>#include<cstdio>#include<algorithm>#include<vector>typedef long long LL;using namespace std;const int N=10005, INF=0x3f3f3f3f;/*----------------------------------------------------------------------------*/template<typename Value, typename Tag>struct Node{int id, l, r;Value val;Tag tag;inline int length()const{return r-l+1;}inline bool disjoint(const int& l_bor, const int& r_bor)const{return l_bor>r || r_bor<l;}// (l, r<l_bor)/(r_bor>l, r)inline bool subset(const int& l_bor, const int& r_bor)const{return l_bor<=l && r_bor>=r;}// [l_bor, l, r, r_bor]};template<typename Value, typename Tag>class SegmentTree{public:typedef Value (*FucMer)(Value, Value);typedef void (*FucCov)(Node<Value, Tag>*, Tag);SegmentTree(const FucMer f1, const FucCov f2, Value val, Tag tag): Merge(f1), Cover(f2), val_zero_(val), tag_zero_(tag) {}void Init(const int& size, const vector<Value>& v){l_range_=1, r_range_=size;nodes_.resize(size<<2);Build(1, l_range_, r_range_, v);}inline Node<Value, Tag>* identify(const int& p){return &nodes_[p];}inline Node<Value, Tag>* l_child(const Node<Value, Tag>* p){return &nodes_[p->id<<1];}// 2*id for the left childinline Node<Value, Tag>* r_child(const Node<Value, Tag>* p){return &nodes_[p->id<<1|1];}// 2*id+1 for the right childvoid Modify(const int& pos, const Tag& tag){Modify(identify(1), pos, pos, tag);}// point changevoid Modify(const int& l_bor, const int& r_bor, const Tag& tag){Modify(identify(1), l_bor, r_bor, tag);}// section changeValue Query(const int& pos){return Query(identify(1), pos, pos);}// point queryValue Query(const int& l_bor, const int& r_bor){return Query(identify(1), l_bor, r_bor);}// section queryprivate:const FucMer Merge;const FucCov Cover;const Value val_zero_;const Tag tag_zero_;int l_range_, r_range_;vector<Node<Value, Tag>> nodes_;inline void PushUp(Node<Value, Tag>* p){p->val=Merge(l_child(p)->val, r_child(p)->val);}inline void PushDown(Node<Value, Tag>* p){Cover(l_child(p), p->tag);Cover(r_child(p), p->tag);p->tag=tag_zero_;}void Build(int cur, int l_cur, int r_cur, const vector<Value>& v){Node<Value, Tag> *p=identify(cur);p->id=cur, p->l=l_cur, p->r=r_cur;p->tag=tag_zero_;if(l_cur>r_cur) return;if(l_cur==r_cur) { p->val=v[l_cur]; return; }int mid=(l_cur+r_cur)>>1;Build(cur<<1, l_cur, mid, v);Build(cur<<1|1, mid+1, r_cur, v);PushUp(p);}void Modify(Node<Value, Tag> *p, const int& l_bor, const int& r_bor,const Tag& tag){if(p->disjoint(l_bor, r_bor)) return;if(p->subset(l_bor, r_bor)) { Cover(p, tag); return; }if(p->tag!=tag_zero_) PushDown(p);Modify(l_child(p), l_bor, r_bor, tag);Modify(r_child(p), l_bor, r_bor, tag);PushUp(p);}Value Query(Node<Value, Tag>* p, const int& l_bor, const int& r_bor){if(p->disjoint(l_bor, r_bor)) return val_zero_;if(p->subset(l_bor, r_bor)) return p->val;if(p->tag!=tag_zero_) PushDown(p);return Merge(Query(l_child(p), l_bor, r_bor),Query(r_child(p), l_bor, r_bor));}};/*----------------------------------------------------------------------------*/auto h1=[](int a, int b) -> int { return a ^ b; };auto h2=[](Node<int, int>* p, int x) { p->val=x; };SegmentTree<int, int> h_xor(h1, h2, 0, 0);void Test(){freopen("temp\\in.txt", "r", stdin);}int main(){// Test();int n, q;scanf("%d%d", &n, &q);vector<int> v;v.push_back(0);for(int i=1, x; i<=n; i++){scanf("%d", &x);v.push_back(x);}h_xor.Init(n, v);while(q--){int a, b;scanf("%d%d", &a, &b);printf("%d\n", h_xor.Query(a, b));}return 0;}
Test details
Test 1
Verdict: ACCEPTED
input |
---|
8 36 7 6 4 6 2 9 4 8 1 1 1 2 1 3 ... |
correct output |
---|
7 1 5 3 1 ... |
user output |
---|
7 1 5 3 1 ... |
Test 2
Verdict: ACCEPTED
input |
---|
200000 200000 921726510 307633388 992247073 ... |
correct output |
---|
834756431 130379787 403037296 308618218 784778243 ... |
user output |
---|
834756431 130379787 403037296 308618218 784778243 ... Truncated |