【HDOJ】4267 A Simple Problem with Integers

树状数组。Easy.

 /* 4267 */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 const int maxn = ;
const int maxm = ;
int n; inline int lowest(int x) {
return -x & x;
} typedef struct arr_t {
int s[maxn]; void clr() {
memset(s, , sizeof(s));
} void update(int x, int delta) {
while (x <= n) {
s[x] += delta;
x += lowest(x);
}
} int sum(int x) {
int ret = ; while (x) {
ret += s[x];
x -= lowest(x);
}
return ret;
}
} arr_t; arr_t ts[maxm];
int A[maxn], M[][maxn];
int ID[][]; void init_() {
int cnt = ; rep(i, , ) {
rep(j, , i) {
ID[i][j] = cnt++;
}
} rep(i, , ) {
int k = i-;
rep(j, , maxn) {
M[k][j] = M[k][j-] + ;
if (M[k][j] == i)
M[k][j] = ;
}
}
} void init() {
rep(i, , maxm)
ts[i].clr();
} void update(int a, int b, int k, int delta) {
int from = a;
int to = a+(b-a)/k*k;
int findex = (from+k-)/k;
int tindex = (to+k-)/k;
int id = ID[k][a%k]; ts[id].update(findex, delta);
ts[id].update(tindex+, -delta);
} int sum(int x) {
int id, index, delta;
int ret = ; rep(i, , ) {
index = (x+i-)/i;
id = ID[i][M[i-][x]];
delta = ts[id].sum(index);
ret += delta;
}
return ret;
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int type;
int a, b, k, c;
int q;
int ans; init_();
while (scanf("%d", &n)!=EOF) {
rep(i, , n+)
scanf("%d", &A[i]);
init();
scanf("%d", &q);
while (q--) {
scanf("%d %d", &type, &a);
if (type == ) {
scanf("%d %d %d", &b, &k, &c);
update(a, b, k, c);
} else {
ans = sum(a) + A[a];
printf("%d\n", ans);
}
}
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}
上一篇:11个常用的Linux命令


下一篇:【HDOJ】1016 Prime Ring Problem