Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- const int mod = 3;
- vector<int> tree;
- void build(vector<int> &a,int v,int l,int r){
- if(l==r)
- tree[v] = a[l];
- else{
- int mid = (l+r)/2;
- build(a,2*v,l,mid);
- build(a,2*v+1,mid+1,r);
- tree[v] = (tree[2*v]+tree[2*v+1])%3;
- }
- }
- int range_sum(int v,int tl,int tr,int l,int r){
- if(l>r)
- return 0;
- if(l==tl and r==tr)
- return tree[v];
- int tm = (tl+tr)/2;
- return (range_sum(2*v,tl,tm,l,min(tm,r))+range_sum(2*v+1,tm+1,tr,max(l,tm+1),r))%3;
- }
- void update(int v,int tl,int tr,int idx,int val){
- if(tl == tr)
- tree[v] = val;
- else{
- int tm = (tl+tr)/2;
- if(idx<=tm)
- update(2*v,tl,tm,idx,val);
- else
- update(2*v+1,tm+1,tr,idx,val);
- tree[v] = (tree[2*v]+tree[2*v+1])%3;
- }
- }
- vector<int> Solution::solve(string s, vector<vector<int> > &queries) {
- const int n = s.size();
- tree.assign(4*n,0);
- vector<int> power(n);
- vector<int> a(n);
- power[0] = 1;
- for(int i=1;i<n;i++){
- power[i] = (power[i-1]*2)%mod;
- }
- reverse(power.begin(),power.end());
- for(int i=0;i<n;i++){
- if(s[i]=='1')
- a[i] = power[i];
- }
- build(a,1,0,n-1);
- vector<int> ans;
- for(auto &q:queries){
- int x = q[0],u = q[1]-1,v = q[2]-1;
- if(x){
- if(s[u]=='0'){
- s[u] = '1';
- a[u] = power[u];
- update(1,0,n-1,u,power[u]);
- }
- ans.push_back(-1);
- }else{
- int curr = range_sum(1,0,n-1,u,v);
- ans.push_back((curr*power[v])%3);
- }
- }
- return ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement