Reku
0%

kd树练习：矩形区域查找

Posted on Edited on In Views: Valine:

建立完kd树之后，对于每个子树，在根的位置记录一下覆盖这颗子树的最小的矩形，然后查询或者修改的时候算一下矩形交，之后就好啦。 不过因为两棵子树都有可能进入，所以我感觉时间复杂度还是比较玄学的，所幸题目上的表现似乎都还可以。 http://www.lydsy.com/JudgeOnline/problem.php?id=4066 比较裸的矩形区域查询，之前试图用最近点的模板魔改一下，结果怎么该都过不去，然后找到了一份合理的板子，搞了一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 200010  
#define ll long long  
using namespace std;  
int n,x1,y1,x2,y2,a,opt,rt,f,P;  
int lastans;  
inline int read(){  
    int x=0,f=1;char ch=getchar();  
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}  
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}  
    return x*f;  
}  
struct use{  
  int d[2],mn[2],mx[2],v,l,r;  
  int sum;  
  inline int &operator[](int x){return d[x];}  
  inline friend bool operator<(use a,use b){return a[f]<b[f]; }   
  inline friend bool operator==(use a,use b){return a.d[0]==b.d[0]&&a.d[1]==b.d[1];}  
}p[N];  
inline bool in(int x1,int y1,int x2,int y2,int a,int b,int c,int d){  
  return x1<=a&&x2>=c&&y1<=b&&y2>=d;  
}  
inline bool out(int x1,int y1,int x2,int y2,int a,int b,int c,int d){  
  return x2<a||x1>c||y1>d||y2<b;  
}  
struct kdtree{  
  use t[N],T;  
  int cnt;  
  inline void update(int k){  
    int l=t[k].l,r=t[k].r;  
    for (int i=0;i<=1;i++){  
      t[k].mn[i]=t[k].mx[i]=t[k][i];  
      if (l) t[k].mn[i]=min(t[k].mn[i],t[l].mn[i]);  
      if (l) t[k].mx[i]=max(t[k].mx[i],t[l].mx[i]);  
      if (r) t[k].mn[i]=min(t[k].mn[i],t[r].mn[i]);  
      if (r) t[k].mx[i]=max(t[k].mx[i],t[r].mx[i]);  
    }  
   t[k].sum=t[l].sum+t[r].sum+t[k].v;  
  }  
  int query(int k,int x1,int y1,int x2,int y2){  
    if (!k) return 0;  
    ll ans(0);  
    if (in(x1,y1,x2,y2,t[k].mn[0],t[k].mn[1],t[k].mx[0],t[k].mx[1]))  
      return t[k].sum;  
    if (out(x1,y1,x2,y2,t[k].mn[0],t[k].mn[1],t[k].mx[0],t[k].mx[1]))  
      return 0;  
    if (in(x1,y1,x2,y2,t[k][0],t[k][1],t[k][0],t[k][1]))  
      ans+=t[k].v;  
    ans+=query(t[k].l,x1,y1,x2,y2)+query(t[k].r,x1,y1,x2,y2);  
    return ans;   
  }  
  void insert(int &k,bool d){  
   if(!k){  
     k=++cnt;  
     t[k][0]=t[k].mn[0]=t[k].mx[0]=T[0];  
     t[k][1]=t[k].mn[1]=t[k].mx[1]=T[1];  
   }  
  if(T==t[k]){  
     t[k].v+=T.v,t[k].sum+=T.v;  
     return;  
  }  
  if(T[d]<t[k][d])insert(t[k].l,d^1);  
  else insert(t[k].r,d^1);  
  update(k);  
 }  
  int rebuild(int l,int r,int d){  
    if (l>r) return 0;f=d;  
    int mid=(l+r)>>1;  
    nth_element(p+l,p+mid,p+r+1);  
    t[mid]=p[mid];  
    t[mid].l=rebuild(l,mid-1,d^1);  
    t[mid].r=rebuild(mid+1,r,d^1);  
    update(mid);return mid;  
  }  
}kd;  
int main(){ 
  n=read();  
  P=5000;
  lastans=0;
  while (1){  
    opt=read(); 
    if (opt==3) break;  
    if (opt==1){  
      x1=read();y1=read();a=read();   
      kd.T[0]=x1;kd.T[1]=y1;kd.T.v=kd.T.sum=a;  
      kd.insert(rt,0);  
      if (kd.cnt==P){  
        for (int j=1;j<=kd.cnt;j++) p[j]=kd.t[j];  
        rt=kd.rebuild(1,kd.cnt,0),P+=5000;  
      }  
    }  
   else{  
      x1=read();y1=read();x2=read();y2=read();   
      lastans=kd.query(rt,x1,y1,x2,y2);  
      printf("%d\n",lastans);  
   }  
  }   
}

http://www.lydsy.com/JudgeOnline/problem.php?id=4154 思路不算难，就是把dfs序和深度作为点，然后染色就变成了矩形区域染色，用线段树的lazy思想处理一下，防止超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#define N 100010  
#define ll long long  
#define pb push_back
using namespace std;  
const ll mod=1e9+7;
ll fans=0;
inline int read(){  
    int x=0,f=1;char ch=getchar();  
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}  
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}  
    return x*f;  
}
int f;
int idx[N];
struct use{  
  int d[2],mn[2],mx[2],l,r,id;  
  int t,c;
  int ts,cs;
  int fa;  
  inline int &operator[](int x){return d[x];}  
  inline friend bool operator<(use a,use b){return a[f]<b[f]; }   
  inline friend bool operator==(use a,use b){return a.d[0]==b.d[0]&&a.d[1]==b.d[1];}  
}p[N];  
inline bool in(int x1,int y1,int x2,int y2,int a,int b,int c,int d){  
  return x1<=a&&x2>=c&&y1<=b&&y2>=d;  
}  
inline bool out(int x1,int y1,int x2,int y2,int a,int b,int c,int d){  
  return x2<a||x1>c||y1>d||y2<b;  
}  
struct kdtree{  
  use t[N],T;  
  int cnt;  
  inline void update(int k){  
    int l=t[k].l,r=t[k].r;  
    for (int i=0;i<=1;i++){  
      t[k].mn[i]=t[k].mx[i]=t[k][i];  
      if (l) t[k].mn[i]=min(t[k].mn[i],t[l].mn[i]);  
      if (l) t[k].mx[i]=max(t[k].mx[i],t[l].mx[i]);  
      if (r) t[k].mn[i]=min(t[k].mn[i],t[r].mn[i]);  
      if (r) t[k].mx[i]=max(t[k].mx[i],t[r].mx[i]);  
    }
  }  
  int rebuild(int l,int r,int d,int fa){  
    if (l>r) return 0;f=d;  
    int mid=(l+r)>>1;  
    nth_element(p+l,p+mid,p+r+1); 
    t[mid]=p[mid];  
    t[mid].fa=fa;
    idx[t[mid].id]=mid;
    t[mid].l=rebuild(l,mid-1,d^1,mid);  
    t[mid].r=rebuild(mid+1,r,d^1,mid); 
    update(mid);
	return mid;  
  }  
  int query(int x)
  {
  	int tt=t[x].ts;
  	int cc=t[x].cs;
  	if(t[x].t>tt)
  	{
  		tt=t[x].t;
  		cc=t[x].c;
	}
  	while(t[x].fa!=0)
  	{
  		x=t[x].fa;
  		if(t[x].t>tt)
  		{
  			tt=t[x].t;
  			cc=t[x].c;
		}
	}
	return cc;
  }
  void up(int k,int tt,int cc,int x1,int y1,int x2,int y2){  
    if (!k) return;  
    if (in(x1,y1,x2,y2,t[k].mn[0],t[k].mn[1],t[k].mx[0],t[k].mx[1]))
	{
		t[k].t=tt;
		t[k].c=cc;
		return;
	}  
    if (out(x1,y1,x2,y2,t[k].mn[0],t[k].mn[1],t[k].mx[0],t[k].mx[1]))  return;
    if (in(x1,y1,x2,y2,t[k][0],t[k][1],t[k][0],t[k][1]))
    {
    	t[k].ts=tt;
    	t[k].cs=cc;
	}
	up(t[k].l,tt,cc,x1,y1,x2,y2);
	up(t[k].r,tt,cc,x1,y1,x2,y2);  
	return; 
  }  
} kd;
vector<int> e[N];
int dfs[N];
int ou[N];
int dep[N];
int u;
void ff(int x,int d)
{
	u++;
	dfs[x]=u;
	dep[x]=d;
	for(int i=0;i<e[x].size();i++)
	{
		ff(e[x][i],d+1);
	}
	ou[x]=u;
}
void work()
{
	int n,c,q;
	n=read(); c=read(); q=read();
	for(int i=1;i<=n;i++) e[i].clear();
	for(int i=2;i<=n;i++)
	{
		int a;
		a=read();
		e[a].pb(i);
	}
	u=0;
	ff(1,1);
	for(int i=1;i<=n;i++)
	{
		p[i].d[0]=p[i].mn[0]=p[i].mx[0]=dfs[i];
		p[i].d[1]=p[i].mn[1]=p[i].mx[1]=dep[i];
		p[i].id=i;
		p[i].ts=0;
		p[i].cs=1;
		p[i].t=0;
		p[i].c=0;
		p[i].l=p[i].r=p[i].fa=0;
	}
	int root=kd.rebuild(1,n,0,0);
	fans=0;
	for(int i=1;i<=q;i++)
	{
		int a,l,c;
		a=read(); l=read(); c=read();
		if(c==0)
		{
			fans+=(ll)kd.query(idx[a])*(ll)i;
			fans%=mod;
		}
		else
		{
			kd.up(root,i,c,dfs[a],dep[a],ou[a],dep[a]+l);
		}
	}
	printf("%lld\n",fans);
}
int main()
{
	int T;
	T=read();
	while(T--) work();
}