本地网站做通用会员卡,4000套微信小游戏源码,常德优化公司,网站制作做网站文章目录前言upd例题P3810 【模板】三维偏序#xff08;陌上花开#xff09;P2487 [SDOI2011]拦截导弹所谓CDQ分治#xff0c;就是和由Conprour、Doctorjellyfish、QE添一同发明的分治算法 #xff08;逃#xff09;
前言
神奇的乱搞黑科技 CDQ分治能够通过更小的时间常…
文章目录前言upd例题P3810 【模板】三维偏序陌上花开P2487 [SDOI2011]拦截导弹所谓CDQ分治就是和由Conprour、Doctorjellyfish、QE添一同发明的分治算法 逃
前言
神奇的乱搞黑科技 CDQ分治能够通过更小的时间常数和更简单的代码难度完爆一些大算法如树套树、splay凸包等。 应用条件询问离线修改独立
upd
from KHIN 归并排序的时候可以直接调用 c98 中的 inplace_merge(l,mid,r,cmp)。 表示把 [l,mid) 和 [mid,r) 的有序数组按照 cmp 排序。
例题
P3810 【模板】三维偏序陌上花开 有n个元素每个元素有三个特征值元素a大于元素b当且仅当a的三个特征值都大于等于b 设 f(i) 表示a大于的元素数量不含自己对于每一个 i 求出 f(x)i 的 x 的数目 n≤2×105n\le 2\times10^5n≤2×105 CDQ分治的经典套路先递归求左右内部贡献再求左右对互相的贡献 先按照x排序然后每次合并的时候两边分别按照y排序利用双指针维护树状数组累加答案即可 时间复杂度O(nlog2n)O(n\log^2n)O(nlog2n) 细节上注意完全相同的元素需要特殊处理树状数组不要忘记清空
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N2e5100;
const int mod998244353;
inline ll read() {ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}int n,m,k;
struct node{int a,b,c,id,w;
}p[N],P[N];
bool cmpa(node u,node v){if(u.a!v.a) return u.av.a;else if(u.b!v.b) return u.bv.b;return u.cv.c;
}
bool cmpb(node u,node v){if(u.b!v.b) return u.bv.b;else return u.cv.c;
}int f[N];
inline void add(int p,int w){for(;pm;pp-p) f[p]w;return;
}
inline int ask(int p){int res(0);for(;p;p-p-p) resf[p];return res;
}int ans[N],bac[N];
void solve(int l,int r){if(lr) return;int mid(lr)1;solve(l,mid);solve(mid1,r);//printf(\nsolve:(%d %d)\n,l,r);sort(pl,pmid1,cmpb);sort(pmid1,pr1,cmpb);int pll;for(int imid1;ir;i){while(plmidp[pl].bp[i].b){add(p[pl].c,p[pl].w);//printf( add: (%d %d %d) w%d\n,p[pl].a,p[pl].b,p[pl].c,p[pl].w);pl;}ans[p[i].id]ask(p[i].c);//printf( query: (%d %d %d) add%d\n,p[i].a,p[i].b,p[i].c,ask(p[i].c));}for(int il;ipl;i) add(p[i].c,-p[i].w);return;
}
int main(){
#ifndef ONLINE_JUDGE//freopen(a.in,r,stdin);//freopen(a.out,w,stdout);
#endifnread();mread();for(int i1;in;i){P[i](node){(int)read(),(int)read(),(int)read()};}sort(P1,P1n,cmpa);int tot(0);for(int i1;in;i){if(i1P[i-1].aP[i].aP[i-1].bP[i].bP[i-1].cP[i].c) p[tot].w;else{p[tot]P[i];p[tot].w1;p[tot].idtot;}}swap(tot,n);solve(1,n);for(int i1;in;i){bac[ans[p[i].id]p[i].w-1]p[i].w;//printf((%d %d %d) ans%d\n,p[i].a,p[i].b,p[i].c,ans[p[i].id]);}for(int i0;itot;i) printf(%d\n,bac[i]);return 0;
}
/*
*/P2487 [SDOI2011]拦截导弹 某国为了防御敌国的导弹袭击发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷虽然它的第一发炮弹能够到达任意的高度、并且能够拦截任意速度的导弹但是以后每一发炮弹都不能高于前一发的高度其拦截的导弹的飞行速度也不能大于前一发。某天雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段所以只有一套系统因此有可能不能拦截所有的导弹。 在不能拦截所有的导弹的情况下我们当然要选择使国家损失最小、也就是拦截导弹的数量最多的方案。但是拦截导弹数量的最多的方案有可能有多个如果有多个最优方案那么我们会随机选取一个作为最终的拦截导弹行动蓝图。 我方间谍已经获取了所有敌军导弹的高度和速度你的任务是计算出在执行上述决策时每枚导弹被拦截掉的概率。 利用CDQ分治优化1D-1D的DP 先递归处理出左半区间的dp值然后尝试用左半区间的dp值更新右半区间再递归处理右半区间 利用树状数组维护前/后缀最大值保证复杂度 时间复杂度O(nlog2n)O(n\log^2n)O(nlog2n) 注意在递归处理右半区间之前需要先按照下标重新sort一下使右半区间重新变得有序
#includebits/stdc.h
using namespace std;
#define ll __int128
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N2e5100;
const int mod1e9;
inline ll read() {ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}int n,m,k;
int q[N],cnt;
struct node{int a,b,id;bool operator (const node o){return ao.a;}
}p[N];
bool cmp(node u,node v){return u.idv.id;
}
struct Dp{int val;ll num;
}dp1[N],dp2[N];
void operator (Dp a,Dp b){if(b.vala.val) ab;else if(b.vala.val) a.numb.num;return;
}Dp f[N];
inline void Upd(int p,Dp w){for(;pcnt;pp-p) f[p]w;return;
}
inline Dp Ask(int p){Dp res(Dp){0,0};for(;p;p-p-p) resf[p];return res;
}
inline void Clear(int p){for(;pcnt;pp-p) f[p](Dp){0,0};return;
}
void solve2(int l,int r){if(lr){dp2[l].val;return;}int mid(lr)1;solve2(mid1,r);//printf(\nsolve: (%d %d)\n,l,r);sort(pl,pmid1);sort(pmid1,pr1);int plr;for(int imid;il;i--){while(plmidp[pl].ap[i].a){Upd(p[pl].b,dp2[p[pl].id]);//printf( add: i%d DP:(%d %d)\n,p[pl].id,dp2[pl].val,(int)dp2[pl].num);--pl;}dp2[p[i].id]Ask(p[i].b);//printf( update: i%d DP:(%d %d)\n,p[i].id,dp2[i].val,(int)dp2[i].num);}for(int ir;ipl;i--) Clear(p[i].b);sort(pl,pmid1,cmp);solve2(l,mid);return;
}inline void upd(int p,Dp w){pcnt-p1;for(;pcnt;pp-p) f[p]w;return;
}
inline Dp ask(int p){pcnt-p1;Dp res(Dp){0,0};for(;p;p-p-p) resf[p];return res;
}
inline void clear(int p){pcnt-p1;for(;pcnt;pp-p) f[p](Dp){0,0};return;
}
void solve1(int l,int r){if(lr){dp1[l].val;return;}int mid(lr)1;solve1(l,mid);sort(pl,pmid1);sort(pmid1,pr1);//printf(\nsolve: (%d %d)\n,l,r);int pll;for(int imid1;ir;i){while(plmidp[pl].ap[i].a){upd(p[pl].b,dp1[p[pl].id]);pl;//printf( add: i%d DP:(%d %d)\n,p[i].id,dp1[i].val,(int)dp1[i].num);}dp1[p[i].id]ask(p[i].b);//printf( update: i%d DP:(%d %d)\n,p[i].id,dp1[i].val,(int)dp1[i].num);}for(int il;ipl;i) clear(p[i].b);sort(pmid1,pr1,cmp);solve1(mid1,r);return;
}int main(){
#ifndef ONLINE_JUDGE//freopen(a.in,r,stdin);//freopen(a.out,w,stdout);
#endifnread();for(int i1;in;i){p[i].aread();p[i].bread();p[i].idi;dp1[i].numdp2[i].num1;q[cnt]p[i].a;q[cnt]p[i].b;}sort(q1,q1cnt);cntunique(q1,q1cnt)-q-1;for(int i1;in;i){p[i].alower_bound(q1,q1cnt,p[i].a)-q;p[i].blower_bound(q1,q1cnt,p[i].b)-q;}solve1(1,n);sort(p1,p1n,cmp);solve2(1,n);ll sum0;int ans(0);for(int i1;in;i){if(dp1[i].valans){ansdp1[i].val;sumdp1[i].num;}else if(dp1[i].valans){sumdp1[i].num;}}printf(%d\n,ans);for(int i1;in;i){//printf(i%d dp1(%d %d) dp2(%d %d)\n,i,dp1[i].val,(int)dp1[i].num,dp2[i].val,(int)dp2[i].num);if(dp1[i].valdp2[i].val-1ans){printf(%.5lf ,1.0*dp1[i].num*dp2[i].num/sum);}else printf(0.00000 );}return 0;
}
/*
10
23 7
63 14
84 57
40 74
96 79
20 27
48 37
86 70
66 28
86 47
*/
