Mantouiqui's blog

sqrt_decomposition HELP
By Mantouiqui, 11 years ago, In English

I am trying to solve this problem using sqrt_decomposition : http://www.spoj.com/problems/HORRIBLE/ Getting WA

Strategy used : 1. Two arrays, b for storing range sum, c for storing range change. 2. Whenever requested update, range which do not lie completely in a block is individually updated where as for a block range update only c. 3. same can be considered for query.


#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#define ll long long int
using namespace std;

int n, q, type, x, y, k;
ll a[10000000], b[1000000], c[1000000];
int bs, cnt;

void sqrt_decomposition() {

    bs = (int) sqrt(n + .0) + 1;
    
}

void update(int l, int r, int k) {

    int cl = l / bs, cr = r / bs;

    if(cl == cr) {

        for(int i = l; i <= r; ++i) {
            b[cl] += k - a[i];
            a[i] += k;
        }

    }

    else {

        for(int i = l, end = (cl + 1) * bs - 1; i <= end; ++i) {
            b[cl] += k - a[i];
            a[i] += k;
        }

        for(int i = (cl + 1); i <= (cr - 1); ++i) {
            c[i] += k;
        }

        for(int i = cr * bs; i <= r; ++i) {
            b[cr] += k - a[i];
            a[i] += k;
        }

    }
}

ll query(int l, int r) {

    int cl = l / bs, cr = r / bs;
    ll sum = 0;

    if(cl == cr) {

        for(int i = l; i <= r; ++i)
            sum += a[i] + c[cl];
    }

    else {

        for(int i = l, end = (cl + 1) * bs - 1; i <= end; ++i) {
            sum += a[i] + c[cl];
        }

        for(int i = (cl + 1); i <= (cr - 1); ++i) {
            sum += b[i] + bs * c[i];
        }

        for(int i = cr * bs; i <= r; ++i) {
            sum += a[i] + c[cr];
        }

    }

    return sum;
}

int main() {

    ios_base::sync_with_stdio(false);

    int test;
    cin >> test;

    while(test--) {

        cin >> n >> q;

        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(c, 0, sizeof(c));

        sqrt_decomposition();

        while(q--) {

            cin >> type;

            if(type) {
                cin >> x >> y;
                cout << query(x - 1, y - 1) << endl;
            }

            else {
                cin >> x >> y >> k;
                update(x - 1, y - 1, k);
            }
        }

    }

    return 0;
}

Please Help.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

u need to use Segment Tree to solve this problem.
using this data structure, each update and query operation takes . so overall complexity will be .

EDIT: just post here if u want more details. i can explain.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes you are correct. But I should get TLE though not WA. Can you please point out mistake??

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      one thing i can tell without analyzing ur code in-depth is that sqrt function is not needed to solve this problem.

      i will post more once i understand ur code better.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I used it for initializing block size each time for new 'n'.

        → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i think you should take care of the case when x>y (u need to swap them before doing the relevant operations).

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have successfully implemented segment tree for this. I want to solve this using sqrt_decomposition.

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Didn't manage to find a bug, but the for following test case your program gives a wrong output:
10 4
0 4 7 9
0 7 8 8
1 2 9
1 4 6

Your output:
43
27

Correct output:
52
27

Hope this helps :)

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

The problem is in b[cl] += k - a[i] lines. You don't have to subtract a[i] — sum in block changes only by k. With that modification your code got accepted. Modified version.

→ Reply