# BZOJ2683: 简单题(cdq分治 树状数组)

Time Limit: 50 Sec  Memory Limit: 128 MB

Submit: 2142  Solved: 874

[Submit][Status][Discuss]

## Description

1 x y A

1<=x,y<=N，A是正整数

2 x1 y1 x2 y2

1<=x1<= x2<=N 1<=y1<= y2<=N

3

## Sample Input

4 1 2 3 3 2 1 1 3 3 1 2 2 2 2 2 2 3 4 3

3 5

## HINT

1<=N<=500000,操作数不超过200000个，内存限制20M。

## Source

cdq分治裸题。

```#include<cstdio>
#include<algorithm>
#define lowbit(x) ((x) & (-x))
using namespace std;
const int MAXN = 5 * 1e5 + 10;
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, Qnum;
struct Query {
int opt, x, y, v, ans, xxx;
bool operator < (const Query &rhs) const {
return x == rhs.x ? y < rhs.y : x < rhs.x;
}
}Q[MAXN], Tp[MAXN];
int T[MAXN];
void Add(int pos, int val) {
for(int i = pos; i <= N; i += lowbit(i)) T[i] += val;
}
int Sum(int pos) {
int ans = 0;
for(int i = pos; i; i -= lowbit(i)) ans += T[i];
return ans;
}
int num = 0, out[MAXN];
void CDQ(int l, int r) {
if(l == r) return ;
int mid = l + r >> 1;
CDQ(l, mid);
CDQ(mid + 1, r);
int i = l, j = mid + 1, p = l, last = 0;
sort(Q + l, Q + mid + 1);
sort(Q + mid + 1, Q + r + 1);
while(j <= r) {
while(Q[i].opt == 2 && i <= mid) i++;
while(Q[j].opt == 1 && j <= r) j++;
if(i <= mid && Q[i].x <= Q[j].x) Add(Q[i].y, Q[i].v), last = i++;
else if(j <= r) Q[j].ans += Sum(Q[j].y), j++;
}
for(int i = l; i <= last; i++)
if(Q[i].opt == 1)

}
int main() {
for(;;) {
if(op == 3) break;
else {
Qnum++;
Q[++num] = (Query) {op, xx2, yy2, 1, 0, Qnum};
Q[++num] = (Query) {op, xx1 - 1, yy1 - 1, 2, 0, Qnum};
Q[++num] = (Query) {op, xx1 - 1, yy2, 3, 0, Qnum};
Q[++num] = (Query) {op, xx2, yy1 - 1, 4, 0, Qnum};
}
}
CDQ(1, num);
for(int i = 1; i <= num; i++) {
if(Q[i].opt == 2) {
if(Q[i].v == 1 || Q[i].v == 2) out[Q[i].xxx] += Q[i].ans;
else out[Q[i].xxx] -= Q[i].ans;
}
}
for(int i = 1; i <= Qnum; i++)
printf("%d\n", out[i]);
return 0;
}```

0 条评论

• ### cf914D. Bash and a Tough Math Puzzle(线段树)

可以这么想，如果能成功的话，我们可以把那个数改成\$1\$，这样比\$x\$大的数就不会对答案产生影响了。

• ### BZOJ4364: [IOI2014]wall砖墙(线段树)

但实际上因为这题只需要输出最后的操作序列，那么我们只维护最大最小值的覆盖标记即可。

• ### HDU 2689 Sort it【树状数组】

Sort it Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (J...

• ### cf914D. Bash and a Tough Math Puzzle(线段树)

可以这么想，如果能成功的话，我们可以把那个数改成\$1\$，这样比\$x\$大的数就不会对答案产生影响了。

• ### C++版 - 剑指offer面试题38：数字在已排序数组中出现的次数

提交网址： http://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2?tpId=13&...

• ### BZOJ4364: [IOI2014]wall砖墙(线段树)

但实际上因为这题只需要输出最后的操作序列，那么我们只维护最大最小值的覆盖标记即可。

• ### P1341 无序字母对

题目描述 给定n个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。...

• ### AtCoder Beginner Contest 182 A~E

B 题意：就是找到一个数能被尽可能多的a[]数组里面的数整除。找到这个数输出就行了。 因为只有1000，我们直接暴力即可。

• ### HDU 5677 ztr loves substring（回文串加多重背包）

ztr loves substring Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 655...