[DS记录]P6783 [Ynoi2008]rrusq
command_block
·
·
个人记录
题意 : 在二维平面上，有 n 个关键点，m 个矩形，以及 q 个询问，每个关键点有权值 a_i。
每次询问给定 [l,r]，对于一个关键点 i ，如果点 i 在编号在 [l,r] 内的任意一个矩形中，则认为 i 被区间 [l,r] 的矩形并包含。
输出区间 [l,r] 的矩形并包含的所有关键点的权值和。
允许离线。
------------
- 首先考虑一维的子问题 : 区间线段并权值和。
考虑离线，从左到右加入线段，设 $t_i$ 为包含 $i$ 号点的编号最大的线段。
若加入到第 $r$ 条线段，查询 $[l,r]$ ，则所有 $l\leq t_i$ 的点都可以贡献。
设 $s[i]$ 为 $t=i$ 的点的权值和，其区间和即为答案。
每次加入一条线段，会使得一个区间的 $t_i$ 变成 $r$。
可以使用线段树维护，给一个区间打上标记，表示其中的 $t$ 同为某值。
显然，一个点上方恰有一个标记。
修改时，将标记下推，然后一口气将子树内所有标记回收掉，最后打上新的标记。
首先，若需要推标记，则表明子树内无标记，这样只会有 $O(\log n)$ 此标记的更新。
若子树内有标记，产生方法有两种 :
- 推过后没有回收的。显然每次最多产生两个，左右各一个。
- 本来就在那里，从来没被碰过。
综上，这类区间最多 $O(n)$ 个。
每次回收标记和打标记会让一些点的 $t$ 改变，相当于对 $s$ 单点修改。
------------
- 回到二维问题
我们使用 $\rm KDT$ 来把矩形拆成 $O(\sqrt{n})$ 个点的区间。
则一共会有 $O(n\sqrt{n})$ 次标记更新，配合 $O(1)-O(\sqrt{n})$ 的分块求和。
复杂度为 $O((n+q)\sqrt{n})$。
分块部分可以继续优化，但是由于常数小并没有必要。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cmath>
#define pb push_back
#define MaxN 100500
#define MaxM 1000500
using namespace std;
struct SumDS{
int BS,c[MaxN],o[MaxN];
void add(int p,int x)
{c[p]+=x;o[p/BS]+=x;}
int qry(int l,int r)
{
int ret=0,bl=l/BS,br=r/BS;
if (bl==br){
for (int i=l;i<=r;i++)
ret+=c[i];
}else {
for (int i=bl+1;i<br;i++)ret+=o[i];
bl=(bl+1)*BS;br=br*BS;
for (int i=l;i<bl;i++)ret+=c[i];
for (int i=br;i<=r;i++)ret+=c[i];
}return ret;
}
}T;
struct Node{int xl,yl,xr,yr,s,tg;}a[MaxN<<2];
struct Point{int x,y,v;}p[MaxN];
bool cmpX(const Point &A,const Point &B)
{return A.x<B.x;}
bool cmpY(const Point &A,const Point &B)
{return A.y<B.y;}
void build(int l,int r,int u,bool kd)
{
a[u].tg=-1;
if (l==r){
a[u].xl=a[u].xr=p[l].x;
a[u].yl=a[u].yr=p[l].y;
a[u].s=p[l].v;
return ;
}int mid=(l+r)>>1;
nth_element(p+l,p+mid,p+r+1,kd ? cmpX : cmpY);
build(l,mid,u<<1,!kd);
build(mid+1,r,u<<1|1,!kd);
int ls=u<<1,rs=u<<1|1;
a[u].s=a[ls].s+a[rs].s;
a[u].xl=min(a[ls].xl,a[rs].xl);
a[u].yl=min(a[ls].yl,a[rs].yl);
a[u].xr=max(a[ls].xr,a[rs].xr);
a[u].yr=max(a[ls].yr,a[rs].yr);
}
inline void ladd(int u)
{
if (a[u].tg>-1){
a[u<<1].tg=a[u].tg;
a[u<<1|1].tg=a[u].tg;
a[u].tg=-1;
}
}
void clr(int u)
{
if (a[u].tg>-1){
T.add(a[u].tg,-a[u].s);
a[u].tg=-1;
return ;
}clr(u<<1);clr(u<<1|1);
}
Node s[MaxM],wf;
void mdf(int u=1)
{
if (wf.xr<a[u].xl||a[u].xr<wf.xl||wf.yr<a[u].yl|a[u].yr<wf.yl)return ;
if (wf.xl<=a[u].xl&&a[u].xr<=wf.xr&&wf.yl<=a[u].yl&&a[u].yr<=wf.yr){
clr(u);
T.add(a[u].tg=wf.tg,a[u].s);
return ;
}ladd(u);
mdf(u<<1);mdf(u<<1|1);
}
struct Data{int l,p;};
vector<Data> b[MaxN];
int n,m,q,ans[MaxM];
int main()
{
scanf("%d",&n);
T.BS=sqrt(n);
for (int i=1;i<=n;i++){
p[i].x=i;
scanf("%d%d",&p[i].y,&p[i].v);
}build(1,n,1,0);a[1].tg=0;
scanf("%d",&m);
for (int i=1;i<=m;i++)
scanf("%d%d%d%d",&s[i].xl,&s[i].xr,&s[i].yl,&s[i].yr);
scanf("%d",&q);
for (int i=1,l,r;i<=q;i++){
scanf("%d%d",&l,&r);
b[r].pb((Data){l,i});
}
for (int i=1;i<=m;i++){
wf=s[i];wf.tg=i;mdf();
for (int j=0;j<b[i].size();j++)
ans[b[i][j].p]=T.qry(b[i][j].l,i);
}
for (int i=1;i<=q;i++)
printf("%d\n",ans[i]);
return 0;
}
```