BZOJ 4066 简单题

题目链接http://www.lydsy.com/JudgeOnline/problem.php?id=4066

题意:略。

思路
- 插入:新建一个节点,坐标为(x,y),权值为A,插入到KDTree中。
- 查询:将之前的目标点改成目标矩形区域就好了。如果接下来要查的区域完全被包含于目标矩形区域,那就跟线段树区间查询一样直接返回区域和就好了;否则,如果接下来要查的区域与目标区域有交集,就往下查,否则不查。
- 由于插入的时候如果一直往一个区域加点会导致KDTree不平衡而使插入/查询效率退化的情况,所以这里我们要把替罪羊树重构的方法直接搬到KDTree上来,即设定一个常数因子,如果子树的节点数大于这颗树的节点数乘以常数因子,那么我们就直接把这棵树拍平重构使之平衡,看似暴力但效率可观,复杂度并不会改变。

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define fac 0.65
#define ls t[root].s[0]
#define rs t[root].s[1]
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define F first
#define S second
using namespace std;
typedef long long ll;
const int maxn=200000+5;
const int INF=0x3f3f3f3f;
const int P=1000000007;
const double PI=acos(-1.0);
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
template <class T1, class T2>inline void gmax(T1 &a,T2 b){if (b>a) a=b;}
template <class T1, class T2>inline void gmin(T1 &a,T2 b){if (b<a) a=b;}
int N,n,op,D,root,pt,lastans,x,y,A,X0,X1,Y0,Y1,po[maxn];
struct node{
    int d[2],s[2],x[2],y[2],w,sum,sz,ty;
    void setup(int xx,int yy,int v){
        s[0]=s[1]=0,x[0]=x[1]=d[0]=xx,y[0]=y[1]=d[1]=yy,sum=w=v,sz=1;
    }
    void init(){
        x[0]=x[1]=d[0],y[0]=y[1]=d[1];
        s[0]=s[1]=0,sum=w,sz=1;
    }
}t[maxn];
bool cmp(const int&a,const int&b){return t[a].d[D]<t[b].d[D];}
void umax(int&a,int b){if(a<b)a=b;}
void umin(int&a,int b){if(a>b)a=b;}
void maintain(int f,int x){
    t[f].sum+=t[x].sum,t[f].sz+=t[x].sz;
    umin(t[f].x[0],t[x].x[0]),umax(t[f].x[1],t[x].x[1]);
    umin(t[f].y[0],t[x].y[0]),umax(t[f].y[1],t[x].y[1]);
}
int rebuild(int l,int r,int d){
    D=d;int mid=l+((r-l)>>1),root;
    nth_element(po+l,po+mid,po+r+1,cmp);
    root=po[mid];
    t[root].init(),t[root].ty=d;
    if (l<mid) ls=rebuild(l,mid-1,d^1),maintain(root,ls);
    if (mid<r) rs=rebuild(mid+1,r,d^1),maintain(root,rs);
    return root;
}
void dfs(int root){
    po[++pt]=root;
    if (ls) dfs(ls);
    if (rs) dfs(rs);
}
int ins(int p,int x){
    if (!p) return t[x].ty=D^1,x;
    maintain(p,x);
    D=t[p].ty;
    int&nxt=t[p].s[t[x].d[D]>=t[p].d[D]];
    if (t[nxt].sz>t[p].sz*fac)
        return po[pt=1]=x,dfs(p),p==root?root=rebuild(1,pt,t[p].ty):rebuild(1,pt,t[p].ty);
    nxt=ins(nxt,x);
    return p;
}
#define ok(a) (a.x[0]<=X1&&X0<=a.x[1]&&a.y[0]<=Y1&&Y0<=a.y[1])
void query(int root){
    if (X0<=t[root].x[0]&&t[root].x[1]<=X1
        &&Y0<=t[root].y[0]&&t[root].y[1]<=Y1){
        lastans+=t[root].sum;
        return;
    }
    if (X0<=t[root].d[0]&&t[root].d[0]<=X1
        &&Y0<=t[root].d[1]&&t[root].d[1]<=Y1) lastans+=t[root].w;
    if (ls&&ok(t[ls])) query(ls);
    if (rs&&ok(t[rs])) query(rs);
}
int main(){
    read(N);
    t[root=++n].setup(0,0,0);
    while (read(op),op!=3){
        if (op==1){
            read(x),read(y),read(A);
            x^=lastans,y^=lastans,A^=lastans;
            t[++n].setup(x,y,A);
            ins(root,n);
        }
        else{
            read(X0),read(Y0),read(X1),read(Y1);
            X0^=lastans,Y0^=lastans,X1^=lastans,Y1^=lastans;
            lastans=0;
            query(root);
            printf("%d\n",lastans);
        }
    }
    return 0;
}

发表评论

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