/category/kd/ zh-CN Sun, 11 Dec 2016 14:51:00 +0800 Sun, 11 Dec 2016 14:51:00 +0800 /archives/97/ /archives/97/ Sun, 11 Dec 2016 14:51:00 +0800 admin [传送门][1] [传送门][2] [传送门][3] 题目大意：单点加，矩阵查询 直接上kdtree就好了，定期暴力重构 1176题代码： ```c++ #include<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)a=b;} template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;} template<typename T> T sqr(T x){return x*x;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) namespace kd { const int D=2,inf=1000000000; char dnow; struct point { int d[D],val; int operator[](int x){return d[x];} }; inline bool operator<(point a,point b) { return a[dnow]<b[dnow]; } inline int dis(point a,point b){int ret=0;for(int i=0;i<D;i++)ret+=abs(a[i]-b[i]);return ret;} struct kdnode { point p; int sum,l[D],r[D],lc,rc; }; int ans,tm=2; point q1,q2,Q,*P; kdnode t[200010]; inline void update(int k) { for(int i=0;i<D;i++) { if(t[k].lc)repl(t[k].l[i],t[t[k].lc].l[i]),repr(t[k].r[i],t[t[k].lc].r[i]); if(t[k].rc)repl(t[k].l[i],t[t[k].rc].l[i]),repr(t[k].r[i],t[t[k].rc].r[i]); } t[k].sum=t[k].p.val+t[t[k].lc].sum+t[t[k].rc].sum; } inline void init(int x) { for(int i=0;i<D;i++)t[x].l[i]=t[x].r[i]=t[x].p[i];t[x].sum=t[x].p.val; } int build(int l,int r,char now) { if(now==D)now=0; dnow=now; int mid=(l+r)>>1,x=tm++; std::nth_element(P+l,P+mid,P+r+1); t[x].p=P[mid]; t[x].lc=t[x].rc=0; init(x); if(l<mid)t[x].lc=build(l,mid-1,now+1); if(r>mid)t[x].rc=build(mid+1,r,now+1); update(x);return x; } void insert(int k,char now) { if(now==D)now=0; if(Q[now]>=t[k].p[now]) { if(t[k].rc) insert(t[k].rc,now+1); else { t[k].rc=tm++;t[t[k].rc].p=Q; init(t[k].rc); } } else { if(t[k].lc) insert(t[k].lc,now+1); else { t[k].lc=tm++;t[t[k].lc].p=Q; init(t[k].lc); } } update(k); } void query(int k,char now) { if(now==D)now=0; bool tag=1; for(int i=0;i<D;i++) if(q1.d[i]>t[k].l[i]||q2.d[i]<t[k].r[i]) tag=0; if(tag){ans+=t[k].sum;return;} tag=1; for(int i=0;i<D;i++) if(q1.d[i]>t[k].p.d[i]||q2.d[i]<t[k].p.d[i]) tag=0; if(tag)ans+=t[k].p.val; tag=1; for(int i=0;i<D;i++) if(now==i) { if(q1.d[i]>t[k].p.d[i]||q2.d[i]<t[k].l[i])tag=0; } else { if(q1.d[i]>t[k].r[i]||q2.d[i]<t[k].l[i])tag=0; } if(tag&&t[k].lc)query(t[k].lc,now+1); tag=1; for(int i=0;i<D;i++) if(now==i) { if(q1.d[i]>t[k].r[i]||q2.d[i]<t[k].p.d[i])tag=0; } else { if(q1.d[i]>t[k].r[i]||q2.d[i]<t[k].l[i])tag=0; } if(tag&&t[k].rc)query(t[k].rc,now+1); } inline void build(point *p,int n){P=p;build(0,n-1,0);} inline int query(point a,point b){ans=0;q1=a,q2=b;query(1,0);return ans;} inline void insert(point p){Q=p;insert(1,0);} } kd::point pp[200000]; int main() { int cx,n=0,opt; kd::point a,b; scanf("%d%*d",&cx); while(1) { scanf("%d",&opt); if(opt==1) { scanf("%d%d%d",&pp[n].d[0],&pp[n].d[1],&pp[n].val); kd::insert(pp[n++]); } else if(opt==2) { scanf("%d%d%d%d",&a.d[0],&a.d[1],&b.d[0],&b.d[1]); printf("%d\n",kd::query(a,b)+cx*(a.d[1]-a.d[0]+1)*(b.d[1]-b.d[0]+1)); } else return 0; if(n>0&&n%10000==0)kd::tm=1,kd::build(pp,n); } } ``` 过不了就适当调参 [1]: http://www.lydsy.com/JudgeOnline/problem.php?id=1176 [2]: http://www.lydsy.com/JudgeOnline/problem.php?id=2683 [3]: http://www.lydsy.com/JudgeOnline/problem.php?id=4066 ]]> 0 /archives/97/#comments /feed/archives/97/