传送门 传送门 传送门

题目大意:单点加,矩阵查询
直接上kdtree就好了,定期暴力重构

1176题代码:

  1. #include<bits/stdc++.h>
  2. typedef unsigned char uchar;
  3. typedef unsigned int uint;
  4. typedef long long ll;
  5. typedef unsigned long long ull;
  6. typedef double db;
  7. typedef long double ldb;
  8. #define xx first
  9. #define yy second
  10. template<typename T> inline T max(T a,T b){return a>b?a:b;}
  11. template<typename T> inline T min(T a,T b){return a<b?a:b;}
  12. template<typename T> inline T abs(T a){return a>0?a:-a;}
  13. template<typename T> inline void repr(T &a,T b){if(a<b)a=b;}
  14. template<typename T> inline void repl(T &a,T b){if(a>b)a=b;}
  15. template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;}
  16. template<typename T> T sqr(T x){return x*x;}
  17. #define mp(a,b) std::make_pair(a,b)
  18. #define pb push_back
  19. #define lb(x) ((x)&(-(x)))
  20. namespace kd
  21. {
  22. const int D=2,inf=1000000000;
  23. char dnow;
  24. struct point
  25. {
  26. int d[D],val;
  27. int operator[](int x){return d[x];}
  28. };
  29. inline bool operator<(point a,point b)
  30. {
  31. return a[dnow]<b[dnow];
  32. }
  33. 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;}
  34. struct kdnode
  35. {
  36. point p;
  37. int sum,l[D],r[D],lc,rc;
  38. };
  39. int ans,tm=2;
  40. point q1,q2,Q,*P;
  41. kdnode t[200010];
  42. inline void update(int k)
  43. {
  44. for(int i=0;i<D;i++)
  45. {
  46. 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]);
  47. 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]);
  48. }
  49. t[k].sum=t[k].p.val+t[t[k].lc].sum+t[t[k].rc].sum;
  50. }
  51. inline void init(int x)
  52. {
  53. 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;
  54. }
  55. int build(int l,int r,char now)
  56. {
  57. if(now==D)now=0;
  58. dnow=now;
  59. int mid=(l+r)>>1,x=tm++;
  60. std::nth_element(P+l,P+mid,P+r+1);
  61. t[x].p=P[mid];
  62. t[x].lc=t[x].rc=0;
  63. init(x);
  64. if(l<mid)t[x].lc=build(l,mid-1,now+1);
  65. if(r>mid)t[x].rc=build(mid+1,r,now+1);
  66. update(x);return x;
  67. }
  68. void insert(int k,char now)
  69. {
  70. if(now==D)now=0;
  71. if(Q[now]>=t[k].p[now])
  72. {
  73. if(t[k].rc)
  74. insert(t[k].rc,now+1);
  75. else
  76. {
  77. t[k].rc=tm++;t[t[k].rc].p=Q;
  78. init(t[k].rc);
  79. }
  80. }
  81. else
  82. {
  83. if(t[k].lc)
  84. insert(t[k].lc,now+1);
  85. else
  86. {
  87. t[k].lc=tm++;t[t[k].lc].p=Q;
  88. init(t[k].lc);
  89. }
  90. }
  91. update(k);
  92. }
  93. void query(int k,char now)
  94. {
  95. if(now==D)now=0;
  96. bool tag=1;
  97. for(int i=0;i<D;i++)
  98. if(q1.d[i]>t[k].l[i]||q2.d[i]<t[k].r[i])
  99. tag=0;
  100. if(tag){ans+=t[k].sum;return;}
  101. tag=1;
  102. for(int i=0;i<D;i++)
  103. if(q1.d[i]>t[k].p.d[i]||q2.d[i]<t[k].p.d[i])
  104. tag=0;
  105. if(tag)ans+=t[k].p.val;
  106. tag=1;
  107. for(int i=0;i<D;i++)
  108. if(now==i)
  109. {
  110. if(q1.d[i]>t[k].p.d[i]||q2.d[i]<t[k].l[i])tag=0;
  111. }
  112. else
  113. {
  114. if(q1.d[i]>t[k].r[i]||q2.d[i]<t[k].l[i])tag=0;
  115. }
  116. if(tag&&t[k].lc)query(t[k].lc,now+1);
  117. tag=1;
  118. for(int i=0;i<D;i++)
  119. if(now==i)
  120. {
  121. if(q1.d[i]>t[k].r[i]||q2.d[i]<t[k].p.d[i])tag=0;
  122. }
  123. else
  124. {
  125. if(q1.d[i]>t[k].r[i]||q2.d[i]<t[k].l[i])tag=0;
  126. }
  127. if(tag&&t[k].rc)query(t[k].rc,now+1);
  128. }
  129. inline void build(point *p,int n){P=p;build(0,n-1,0);}
  130. inline int query(point a,point b){ans=0;q1=a,q2=b;query(1,0);return ans;}
  131. inline void insert(point p){Q=p;insert(1,0);}
  132. }
  133. kd::point pp[200000];
  134. int main()
  135. {
  136. int cx,n=0,opt;
  137. kd::point a,b;
  138. scanf("%d%*d",&cx);
  139. while(1)
  140. {
  141. scanf("%d",&opt);
  142. if(opt==1)
  143. {
  144. scanf("%d%d%d",&pp[n].d[0],&pp[n].d[1],&pp[n].val);
  145. kd::insert(pp[n++]);
  146. }
  147. else if(opt==2)
  148. {
  149. scanf("%d%d%d%d",&a.d[0],&a.d[1],&b.d[0],&b.d[1]);
  150. printf("%d\n",kd::query(a,b)+cx*(a.d[1]-a.d[0]+1)*(b.d[1]-b.d[0]+1));
  151. }
  152. else return 0;
  153. if(n>0&&n%10000==0)kd::tm=1,kd::build(pp,n);
  154. }
  155. }

过不了就适当调参