Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //range update and range query with sqrt decompo
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- const int mod = 1e9 + 7;
- const int N = 5e5 + 10,Sz = 450;
- int n,q,k,arr[N],to_add[Sz+10],sum[Sz+10][1005];
- void Build() {
- for(int i = 0; i < n; i++) {
- sum[i/Sz][arr[i]] ++;
- }
- }
- int query(int l,int r) {
- int ans = 0;
- for(int i = l; i <= r; i++) {
- ans += sum[i][(k-to_add[i])%k];
- }
- return ans;
- }
- void update(int l,int r,int val) {
- for(int i = l; i <= r; i++) {
- to_add[i] += val;
- to_add[i] %= k;
- }
- }
- int main() {
- ios_base::sync_with_stdio(0); cin.tie(0);
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- cin >> n >> q >> k;
- for(int i = 0; i < n; i++) {
- cin >> arr[i];
- arr[i] %= k;
- }
- Build();
- while(q--) {
- int l,r,type;
- cin >> type >> l >> r;
- if(type == 1) {
- int ans = query(l/Sz+1,r/Sz-1);
- int b1 = l / Sz,b2 = r / Sz;
- for(int i = l; i / Sz == b1 && i <=r; i++) {
- if((to_add[i/Sz] + arr[i])%k == 0) ans ++;
- }
- if(b1 != b2)
- for(int i = r; i / Sz == b2 && i >= 0; i--) {
- if((to_add[i/Sz] + arr[i])%k == 0) ans ++;
- }
- cout << ans << "\n";
- }
- else {
- int val;
- cin >> val;
- int b1 = l / Sz,b2 = r / Sz;
- update(b1+1,b2-1,val);
- for(int i = l; i / Sz == b1 && i <=r; i++) {
- sum[i/Sz][arr[i]] --;
- arr[i] += val;
- arr[i] %= k;
- sum[i/Sz][arr[i]] ++;
- }
- if(b1 != b2)
- for(int i = r; i / Sz == b2 && i >= 0; i--) {
- sum[i/Sz][arr[i]] --;
- arr[i] += val;
- arr[i] %= k;
- sum[i/Sz][arr[i]] ++;
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement