Array Transformer

Write a program to transform an array A[1], A[2],..., A[n] according to m instructions. Each instruction (L, R, v, p) means: First, calculate how many numbers from A[L] to A[R] (inclusive) are strictly less than v, call this answer k. Then, change the value of A[p] to u*k/(R - L + 1), here we use integer division (i.e. ignoring fractional part).

Input 

The first line of input contains three integer n, m, u ( 1n300, 000, 1m50, 000, 1u1, 000, 000, 000). Each of the next n lines contains an integer A[i] ( 1A[i]u). Each of the next m lines contains an instruction consisting of four integers L, R, v, p ( 1LRn, 1vu, 1pn).

Output 

Print n lines, one for each integer, the final array.

Sample Input 

10 1 11
1
2
3
4
5
6
7
8
9
10
2 8 6 10

Sample Output 

1
2
3
4
5
6
7
8
9
6

Explanation: There is only one instruction: L = 2, R = 8, v = 6, p = 10. There are 4 numbers (2,3,4,5) less than 6, so k = 4. The new number in A[10] is 11*4/(8 - 2 + 1) = 44/7 = 6.

---

O(sqrt(n)) 於任何操作。
噁心煩人的塊狀表 ...

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define SIZE 550
struct ele {
    int v, idx;
};
ele piece[SIZE][SIZE];
int A[SIZE*SIZE];
bool cmp(ele a, ele b) {
    return a.v < b.v;
}
int query(int l, int r, int v) {
    static int cnt, lp, rp, m, tl, tr;
    cnt = 0;
    tl = l;
    tr = r;
    while(l%SIZE && l <= r) {
        if(A[l] < v)    cnt++;
        l++;
    }
    while((r+1)%SIZE && l <= r) {
        if(A[r] < v)    cnt++;
        r--;
    }
    if(l > r)   return cnt;
    lp = l/SIZE, rp = r/SIZE, v--;
    while(lp <= rp) {
        l = 0, r = SIZE-1;
        while(l < r) {
            m = (l+r+1)>>1;
            if(piece[lp][m].v <= v)
                l = m;
            else
                r = m-1;
        }
        if(piece[lp][l].v > v)    l--;
        cnt += l+1;
        lp++;
    }
    return cnt;
}
int main() {
    int n, m, u, l, r, v, p;
    int i, j, x, y;
    while(scanf("%d %d %d", &n, &m, &u) == 3) {
        for(i = 0, j = (n-1)/SIZE; i < SIZE; i++)
            piece[j][i].v = 2147483647, piece[j][i].idx = -1;
        for(i = 0; i < n; i++) {
            scanf("%d", &A[i]);
            piece[i/SIZE][i%SIZE].v = A[i];
            piece[i/SIZE][i%SIZE].idx = i;
        }
        for(i = (n-1)/SIZE; i >= 0; i--)
            sort(piece[i], piece[i]+SIZE, cmp);
        /*for(i = 0; i <= psize; i++, puts(""))
            for(j = 0; j < pidx[i]; j++)
                printf("%d ", piece[i][j].v);*/
        while(m--) {
            scanf("%d %d %d %d", &l, &r, &v, &p);
            l--, r--, p--;
            x = query(l, r, v);
            y = (int)((long long)x*u/(r-l+1));
            x = p/SIZE;
            for(i = 0; piece[x][i].idx != p; i++);
            for(; i < SIZE; i++) {
                piece[x][i].v = piece[x][i+1].v;
                piece[x][i].idx = piece[x][i+1].idx;
            }
            for(i = SIZE-2; i >= 0 && piece[x][i].v > y; i--) {
                piece[x][i+1].v = piece[x][i].v;
                piece[x][i+1].idx = piece[x][i].idx;
            }
            piece[x][i+1].v = y;
            piece[x][i+1].idx = p;
            A[p] = y;
        }
        for(i = 0; i < n; i++)
            printf("%d\n", A[i]);
    }
    return 0;
}

---