[UVA][塊狀表] 12003 - Array Transformer
Array Transformer
| 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 (
1
n300, 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;
}