重修 CDQ 分治
简介
把动态问题转化为静态问题。
\[\large{动态问题\xrightarrow{CDQ}静态问题+\log\uparrow} \]静态问题：没有修改操作的问题，或者所有查询操作都在修改操作之后的问题
动态问题：修改和查询操作交叉的问题
例题
P3810 【模板】三维偏序（陌上花开）
就是个模板。
P4390 [BOI2007]Mokia 摩基亚
我们按照时间分治 \(solve(l,r)\)：
-
先 \(solve(l,mid)\)，因为时间无后效性。
-
再计算 \([l,mid]\) 的加点操作给 \([mid+1,r]\) 的贡献。
-
最后，由于 \([l,mid]\) 对 \([mid+1,r]\) 的贡献已经算完，直接放心 \(solve(mid+1,r)\)。
所以这层分治之内唯一要解决的就是第二步。
求矩形和可以二维差分转化为四个 2-sides 矩形。
所以这道题可转化为静态问题：
给定平面上的一些点（带点权）和一些询问，每次询问需回答在一个坐标左下角的点权和。
这可以类似扫描线解决。
点击查看代码
//We'll be counting stars.
//#pragma GCC optimize("Ofast")
#include
using namespace std;
#define IOS ios::sync_with_stdio(false)
#define fir first
#define sec second
#define mkp make_pair
#define pb emplace_back
#define mem(x,y) memset(x,y,sizeof(x))
#define For(i,j,k) for(int i=j;i<=k;i++)
#define Rof(i,j,k) for(int i=j;i>=k;i--)
#define Fe(x,y) for(int x=head[y];x;x=e[x].nxt)
#define ckmx(a,b) a=max(a,b)
#define ckmn(a,b) a=min(a,b)
#define fin(s) freopen(s,"r",stdin)
#define fout(s) freopen(s,"w",stdout)
#define file(s) fin(s".in");fout(s".out")
#define debug cerr<<"Passed line #"<<__LINE__<::min()<<"~"<::max()<>=1;}return r;}
inline void mad(ll &a,ll b){a=(a+b)%mod;while(a<0)a+=mod;}
inline void mmu(ll &a,ll b){a=(a*b)%mod;while(a<0)a+=mod;}
#define inv(a) pw(a,mod-2)
#define int long long
#define N 170010
#define V 2000001
#define low (x&(-x))
int n=0,lim,ans[N],c[V],buf[V],tot=0;
bool vis[V];
inline void add(int x,int y){
while(x<=lim){
c[x]+=y;
if(!vis[x]){
vis[x]=1;
buf[++tot]=x;
}
x+=low;
}
}
inline int que(int x){
int res=0;
while(x){
res+=c[x];
x-=low;
}
return res;
}
inline void clear(){
int x;
while(tot){
x=buf[tot--];
vis[x]=0;
c[x]=0;
}
}
struct Que{
bool opt;//0 add 1 que
int x,y,k,co;
friend bool operator<(Que x,Que y){
if(x.x!=y.x) return x.x>1)
void work(int l,int r){
if(l==r) return ;
work(l,mid);
bt=0;
For(i,l,mid) if(!a[i].opt) b[++bt]=(Que){0,a[i].x,a[i].y,a[i].k,0};
For(i,mid+1,r) if(a[i].opt){
b[++bt]=(Que){1,a[i].xx ,a[i].yy ,i, 1};
b[++bt]=(Que){1,a[i].xx ,a[i].y-1,i,-1};
b[++bt]=(Que){1,a[i].x-1,a[i].yy ,i,-1};
b[++bt]=(Que){1,a[i].x-1,a[i].y-1,i, 1};
}
sort(b+1,b+1+bt);
For(i,1,bt)
if(!b[i].opt) add(b[i].y,b[i].k);
else ans[b[i].k]+=b[i].co*que(b[i].y);
clear();
work(mid+1,r);
}
int32_t main(){IOS;
int x;
cin>>x>>lim;
while(1){
cin>>x;
if(x==3) break;
n++;
a[n].opt=x-1;
if(!a[n].opt) cin>>a[n].x>>a[n].y>>a[n].k;
else cin>>a[n].x>>a[n].y>>a[n].xx>>a[n].yy;
}
work(1,n);
For(i,1,n) if(a[i].opt) cout< P2487 [SDOI2011]拦截导弹
也类似模板，但是要算概率，直接古典概型上即可。
点击查看代码
//We'll be counting stars.
//#pragma GCC optimize("Ofast")
#include
using namespace std;
#define IOS ios::sync_with_stdio(false)
#define fir first
#define sec second
#define mkp make_pair
#define pb emplace_back
#define mem(x,y) memset(x,y,sizeof(x))
#define For(i,j,k) for(int i=j;i<=k;i++)
#define Rof(i,j,k) for(int i=j;i>=k;i--)
#define Fe(x,y) for(int x=head[y];x;x=e[x].nxt)
#define ckmx(a,b) a=max(a,b)
#define ckmn(a,b) a=min(a,b)
#define fin(s) freopen(s,"r",stdin)
#define fout(s) freopen(s,"w",stdout)
#define file(s) fin(s".in");fout(s".out")
#define debug cerr<<"Passed line #"<<__LINE__<::min()<<"~"<::max()<
struct Node{
int x,y,id;
friend bool operator<(Node x,Node y){return x.idy.x;}
int n,s[N],lim,st[N],tot=0;
struct node{
int mxlen;
db cnt;
void init(){mxlen=cnt=1;}
void clear(){mxlen=-1;cnt=0;}
friend node operator+(node x,node y){
if(x.mxlen==y.mxlen) return (node){x.mxlen,x.cnt+y.cnt};
else return x.mxlen>y.mxlen?x:y;
}
friend void operator+=(node &x,node y){x=x+y;}
}t[N<<2],f[2][N];
void lisan(){//lisan for a.y
For(i,1,n) s[i]=a[i].y;
sort(s+1,s+1+n);
lim=unique(s+1,s+1+n)-s-1;
For(i,1,n) a[i].y=lower_bound(s+1,s+1+lim,a[i].y)-s;
}
#define mid ((l+r)>>1)
#define ls (rt<<1)
#define rs (rt<<1|1)
void build(int rt,int l,int r){
t[rt].clear();
if(l==r) return ;
build(ls,l,mid);
build(rs,mid+1,r);
}
void add(int rt,int l,int r,int x,node val){
if(l==r){
// cout<mid) return que(rs,mid+1,r,x,y);
return que(ls,l,mid,x,mid)+que(rs,mid+1,r,mid+1,y);
}
void clear(){
int x;
while(tot){
x=st[tot--];
while(x && t[x].mxlen!=-1){
t[x].clear();
x>>=1;
}
}
}
node addlen(node x){x.mxlen++;return x;}
void solve(int l,int r){
if(l==r) return ;
// cout<<"solve "<>n;
For(i,1,n) cin>>a[i].x>>a[i].y;
lisan();
build(1,1,lim);
cout<"< P4169 [Violet]天使玩偶/SJY摆棋子
不是那个 sjy
发现哈密尔顿距离不好搞，我们将绝对值拆开，每次询问拆成左下左上右下右上四个子问题的最小值。
那和 P4390 [BOI2007]Mokia 摩基亚 不就类似了？
点击查看代码
//We'll be counting stars.
#include
using namespace std;
#define For(i,j,k) for(int i=j;i<=k;i++)
#define Rof(i,j,k) for(int i=j;i>=k;i--)
#define ckmx(a,b) a=max(a,b)
#define ckmn(a,b) a=min(a,b)
#define N 600010
#define V 1000002
#define low (x&(-x))
const int inf=1e7;
int c[V],buf[N],bt=0;
void add(int x,int y){
buf[++bt]=x;
while(x>1;
solve(l,mid);
tot=0;
For(i,l,mid) if(!a[i].opt) b[++tot]=(Node){a[i].opt,a[i].x,a[i].y,i};
For(i,mid+1,r) if(a[i].opt) b[++tot]=(Node){a[i].opt,a[i].x,a[i].y,i};
sort(b+1,b+1+tot);
For(i,1,tot)
if(!b[i].opt) add(b[i].y,b[i].x+b[i].y);
else x=que(b[i].y),ckmn(f[b[i].id],x?b[i].x+b[i].y-x:inf);
clear();
solve(mid+1,r);
}
int32_t main(){
scanf("%d%d",&n,&m);
For(i,1,n) scanf("%d%d",&a[i].x,&a[i].y);
For(i,1,n) a[i].opt=0;
int x;
For(i,n+1,n+m){
scanf("%d%d%d",&x,&a[i].x,&a[i].y);
a[i].opt=x-1;
}
n+=m;
For(i,1,n) a[i].x++;
For(i,1,n) a[i].y++;
For(i,1,n) f[i]=inf;
solve(1,n);
For(i,1,n) a[i].x=V+1-a[i].x;
solve(1,n);
For(i,1,n) a[i].y=V+1-a[i].y;
solve(1,n);
For(i,1,n) a[i].x=V+1-a[i].x;
solve(1,n);
For(i,1,n) if(a[i].opt) printf("%d\n",f[i]);
return 0;}