fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct {
  4. 	unordered_map<int,int> m;	
  5. }seg[2000001];
  6. unordered_map<int,int> merge(unordered_map<int,int> m1,unordered_map<int,int> m2){
  7. 	unordered_map<int,int> mp=m1;
  8. 	for(auto i:m2) mp[i.first]+=i.second;
  9. 	return mp;
  10. }
  11. void build(int a[],int n,int idx,int l,int r,int k){
  12. 	if(l==r) {seg[idx].m[a[l]%k]++; return;}
  13. 	build(a,n,2*idx,l,(l+r)/2,k);
  14. 	build(a,n,2*idx+1,1+(l+r)/2,r,k);
  15. 	seg[idx].m=merge(seg[idx*2].m,seg[idx*2+1].m);
  16. }
  17. void insert(int idx,int l,int r,int p,int val,int a[],int k){
  18. 	if(l==r){
  19. 		seg[idx].m[a[p]%k]--;
  20. 		seg[idx].m[(a[p]+val)%k]++;
  21. 		return;
  22. 	}
  23. 	int mid=(l+r)/2;
  24. 	if(p>mid) insert(2*idx+1,mid+1,r,p,val,a,k);
  25. 	else if(p<=mid) insert(2*idx,l,mid,p,val,a,k);
  26. 	seg[idx].m=merge(seg[2*idx].m,seg[2*idx+1].m);
  27. }
  28. int query(int idx,int l,int r,int x,int y,int rem){
  29. 	if(l==x && r==y) {
  30. 	    if(seg[idx].m.find(rem)!=seg[idx].m.end()) return seg[idx].m[rem];
  31. 		return 0;
  32. 	}
  33. 	int mid=(l+r)/2;
  34. 	if(x>mid) return query(idx*2+1,mid+1,r,x,y,rem);
  35. 	if(y<=mid) return query(idx*2,l,mid,x,y,rem);
  36. 	return query(idx*2,l,mid,x,mid,rem)+query(idx*2+1,mid+1,r,mid+1,y,rem);
  37. }
  38. int main() {
  39. 	int n,q,k,x,l,r,rem,p,val;
  40. 	cin>>n>>q>>k;
  41. 	int a[n];
  42. 	for(int i=0;i<n;i++) cin>>a[i];
  43. 	build(a,n,1,0,n-1,k);
  44. 	for(int i=0;i<q;i++){
  45. 		cin>>x;
  46. 		if(x==1){
  47. 			cin>>p>>val;
  48. 			p-=1;
  49. 			insert(1,0,n-1,p,val,a,k);
  50. 			a[p]+=val;
  51. 		}
  52. 		else{
  53. 			cin>>l>>r>>rem;
  54. 			l-=1,r-=1;
  55. 			cout<<query(1,0,n-1,l,r,rem)<<endl;
  56. 		}
  57. 	}
  58. 	return 0;
  59. }
Success #stdin #stdout 0.05s 112948KB
comments (?)
stdin
copy 
5 3 5
5 4 3 2 1
2 1 5 3
1 5 9
2 1 5 0
stdout
copy 
1
2
https://ideone.com/QRhsSW
language:
C++14 (gcc 8.3)
created:
4 years 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!