A Simple Problem with Integers
Time Limit: 5000/1500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 323 Accepted Submission(s): 133
Problem Description
Let A1, A2, ... , AN be N elements. You need to deal with two kinds of operations. One type of operation is to add a given number to a few numbers in a given interval. The other is to query the value of some element.
Input
There are a lot of test cases.
The first line contains an integer N. (1 <= N <= 50000)
The second line contains N numbers which are the initial values of A1, A2, ... , AN. (-10,000,000 <= the initial value of Ai <= 10,000,000)
The third line contains an integer Q. (1 <= Q <= 50000)
Each of the following Q lines represents an operation.
"1 a b k c" means adding c to each of Ai which satisfies a <= i <= b and (i - a) % k == 0. (1 <= a <= b <= N, 1 <= k <= 10, -1,000 <= c <= 1,000)
"2 a" means querying the value of Aa. (1 <= a <= N)
The first line contains an integer N. (1 <= N <= 50000)
The second line contains N numbers which are the initial values of A1, A2, ... , AN. (-10,000,000 <= the initial value of Ai <= 10,000,000)
The third line contains an integer Q. (1 <= Q <= 50000)
Each of the following Q lines represents an operation.
"1 a b k c" means adding c to each of Ai which satisfies a <= i <= b and (i - a) % k == 0. (1 <= a <= b <= N, 1 <= k <= 10, -1,000 <= c <= 1,000)
"2 a" means querying the value of Aa. (1 <= a <= N)
Output
For each test case, output several lines to answer all query operations.
Sample Input
4 1 1 1 1 14 2 1 2 2 2 3 2 4 1 2 3 1 2 2 1 2 2 2 3 2 4 1 1 4 2 1 2 1 2 2 2 3 2 4
Sample Output
1 1 1 1 1 3 3 1 2 3 4 1
1 //原来我用插点问线做的，输出sum(temp) - sum(temp-1),一直tle 2 #include <stdio.h> 3 #include <iostream> 4 #include<string.h> 5 using namespace std; 6 7 const int MAXD = 50010; 8 int N, M, d[100][MAXD], a[MAXD]; 9 10 void insert(int k, int x, int v) 11 { 12 for(; x <= N; x += x & -x) 13 d[k][x] += v; 14 } 15 16 void init() 17 { 18 int i, j; 19 for(i = 1; i <= N; i ++) 20 cin>>a[i]; 21 for(i = 0; i < 100; i ++) 22 memset(d[i], 0, sizeof(d[i][0]) * (N + 1)); 23 } 24 25 int query(int id) 26 { 27 int i, k, x, ans = 0; 28 for(i = 1; i <= 10; i ++) 29 { 30 k = (i - 1) * 10 + id % i; 31 for(x = id; x > 0; x -= x & -x) 32 ans += d[k][x]; 33 } 34 return a[id] + ans; 35 } 36 37 void solve() 38 { 39 int i, flag,temp; 40 int a, b, k, c; 41 cin>>M; 42 while(M--) 43 { 44 cin>>flag; 45 if(flag == 1) 46 { 47 cin>>a>>b>>k>>c; 48 b -= (b - a) % k; 49 insert(10 * (k - 1) + a % k, a, c); 50 if(b < N) insert(10 * (k - 1) + b % k, b + 1, -c); 51 } 52 else if(flag == 2) 53 { 54 cin>>temp; 55 cout<<query(temp)<<endl; 56 } 57 } 58 } 59 60 int main() 61 { 62 while(cin>>N) 63 { 64 init(); 65 solve(); 66 } 67 return 0; 68 }
