UVA 12003 Array Transformer-白红宇

UVA 12003 Array Transformer

阅读量：5071 次

发布时间：2019-06-12

本文共 2919 字，大约阅读时间需要 9 分钟。

Array Transformer

Time Limit: 5000ms

Memory Limit: 131072KB

This problem will be judged on

UVA. Original ID:

64-bit integer IO format: %lld Java class name: Main

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 $\le$ n $\le$ 300, 000, 1 $\le$ m $\le$ 50, 000, 1 $\le$ u $\le$ 1, 000, 000, 000). Each of the next n lines contains an integer A[i] ( 1 $\le$ A[i] $\le$ u). Each of the next m lines contains an instruction consisting of four integers L, R, v, p ( 1 $\le$ L $\le$ R $\le$ n, 1 $\le$ v $\le$ u, 1 $\le$ p $\le$ n).

Output

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

Sample Input

10 1 11123456789102 8 6 10

Sample Output

1234567896

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.

解题：分块

参考lrj同学的那本大白

1 #include 
       
         2 using namespace std; 3 typedef long long LL; 4 const int maxn = 300000 + 10; 5 const int SIZE = 4096; 6 int n,m,u,A[maxn],block[maxn/SIZE+1][SIZE]; 7 void init() { 8     scanf("%d%d%d",&n,&m,&u); 9     int b = 0,j = 0;10     for(int i = 0; i < n; ++i) {11         scanf("%d",A+i);12         block[b][j] = A[i];13         if(++j == SIZE) {14             b++;15             j = 0;16         }17     }18     for(int i = 0; i < b; ++i)19         sort(block[i],block[i] + SIZE);20     if(j) sort(block[b],block[b]+j);21 }22 int query(int L,int R,int v) {23     int lb = L/SIZE,rb = R/SIZE,k = 0;24     if(lb == rb) {25         for(int i = L; i <= R; ++i)26             k += (A[i] < v);27     } else {28         for(int i = L; i < (lb+1)*SIZE; ++i)29             if(A[i] < v) ++k;30         for(int i = rb*SIZE; i <= R; ++i)31             if(A[i] < v) ++k;32         for(int i = lb+1; i < rb; ++i)33             k += lower_bound(block[i],block[i]+SIZE,v) - block[i];34     }35     return k;36 }37 void update(int p,int x) {38     if(A[p] == x) return;39     int old = A[p],pos = 0,*B = &block[p/SIZE][0];40     A[p] = x;41     while(B[pos] < old) ++pos;42     B[pos] = x;43     while(pos < SIZE-1 && B[pos] > B[pos + 1]) {44         swap(B[pos],B[pos+1]);45         ++pos;46     }47     while(pos > 0 && B[pos] < B[pos - 1]) {48         swap(B[pos],B[pos-1]);49         --pos;50     }51 }52 int main() {53     init();54     while(m--) {55         int L,R,v,p;56         scanf("%d%d%d%d",&L,&R,&v,&p);57         --L;58         --R;59         --p;60         int k = query(L,R,v);61         update(p,(LL)u*k/(R - L + 1));62     }63     for(int i = 0; i < n; ++i)64         printf("%d\n",A[i]);65     return 0;66 }

View Code

转载于:https://www.cnblogs.com/crackpotisback/p/4693673.html

你可能感兴趣的文章