BZOJ 1935: [SHOI2007]园丁的烦恼 – [树状数组]


题目传送门(BZOJ)
>原文链接<

题解 :

嘛~, 题意说的很明白了, 就是二维数点, 我们把询问离线, 顺便离散化.

首先按x排序, 这样树状数组查前缀的时候就可以不用管x这维了,因为需要减掉的还没加进来.

我们把每个点当成一个插入的操作, 把每个询问当成四个查询的操作, 一起排序, 注意当坐标一样的时候优先插入.

至于四个查询, 就是一个前缀和加容斥, 老套路了.

ans[q[i].id]+=q[i].opt\times query(),

插入时不query(), opt=0插入, opt=1容, opt=-1斥.(理解就好)

代码 :

#include 
#include 
#include 
#include 
#include 
const int N = 10100000;
int c[N], n, m, _, ans[N>>2];
struct node {
    int x,y,id,opt;
    node(){}
    node(int x, int y, int id, int opt) : x(x), y(y), id(id), opt(opt) {}
    bool operator < (const node &a) const {
        return x == a.x? id < a.id: x>2];
inline char nc() {
    static char buf[100000], *p1, *p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int rd() {
    int x=0; char ch=nc();
    while(ch<'0'||ch>'9') ch=nc();
    while(ch>='0'&&ch<='9') x = (x<<1)+(x<<3)+ch - 48,ch = nc();
    return x;
}
void change(int x,int y) {for(int i = x; i

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注