常用的网站建设技术有什么软件,网站建设广州网站建设,北京医院网站建设,塘沽网站制作对CDQ深一步的理解 昨天做了一道CDQ,看了一堆CDQ可做的题,今天又做了一道四维偏序 感觉对CDQ的理解又深了一点,故来写一写现在自己对于CDQ的理解 CDQ其实就是实现了这样的一个问题的转化:\(a_{l} a_{l1} ... a_r (a_l,a_{l1},...,a_{mid}) \text{都小于} (…对CDQ深一步的理解 昨天做了一道CDQ,看了一堆CDQ可做的题,今天又做了一道四维偏序 感觉对CDQ的理解又深了一点,故来写一写现在自己对于CDQ的理解 CDQ其实就是实现了这样的一个问题的转化:\(a_{l} a_{l1} ... a_r (a_l,a_{l1},...,a_{mid}) \text{都小于} (a_{mid1},a{mid2},...,a_r)\) 然后我们就知道这时候左边所有的点都一定小于右边的点 在四维偏序的算法中,那就是左边的点可以对右边的点做出贡献(仅在当前维度下) 这样就强行消除了一个维度的限制. 四维偏序 COGS 2479 题目大意 给定一个有\(n\)个元素的序列元素编号为\(1~n\)每个元素有三个属性\(a,b,c\),求序列中满足\(ij\)且\(a_ia_j\)且\(b_ib_j\)且\(c_ic_j\)的数对\((i,j)\)的个数。 题解 我们把下标也看作一个维度,那么这就是个四维偏序 我们在下标的维度上CDQ 然后记录每个元素在第一次CDQ中是较小的还是较大的. 因为只有较小的元素才能对较大的元素做出贡献 只有较大的元素才能接受较小的元素的影响. 所以我们处理出来后这就变成了一个三维偏序 所以我们在对这个序列(CDQ扫描线树状数组)求三维偏序即可 Code #include cstdio
#include cstring
#include algorithm
using namespace std;
typedef long long ll;
inline void read(int x){x0;char ch;bool flag false;while(chgetchar(),ch!);if(ch -) chgetchar(),flag true;while(x10*xch-0,chgetchar(),ch!);if(flag) x-x;
}
const int maxn 50010;
struct Node{int a,b,c;bool is_sm;Node(){abcis_sm 0;}
}a[maxn],tmp1[maxn],tmp2[maxn];
int c[maxn],n,init_tmp[maxn],ans0;
#define lowbit(x) (x-x)
inline void modify(int x,int y){for(;xn;xlowbit(x)) c[x] y;
}
inline int query(int x){int ret 0;for(;x;x-lowbit(x)) ret c[x];return ret;
}
void solve2(int l,int r){if(l r) return ;int mid lr 1;solve2(l,mid);solve2(mid1,r);int i l,j mid1,k l;Node *a tmp1,*tmp tmp2;init_tmp[0] 0;while(i mid || j r){if((j r) || (i mid a[i].b a[j].b)){if( a[i].is_sm){modify(a[i].c,1);init_tmp[init_tmp[0]] i;}tmp[k] a[i];}else{if(!a[j].is_sm){ans query(a[j].c);}tmp[k] a[j];}}for(int i 1;iinit_tmp[0];i) modify(a[init_tmp[i]].c,-1);copy(tmpl,tmpr1,al);
}
void solve1(int l,int r){if(l r) return ;int mid lr 1;solve1(l,mid);solve1(mid1,r);int i l,j mid1,k l;Node *tmp tmp1;while(i mid || j r){if((j r) || (i mid a[i].a a[j].a)){(tmp[k] a[i]).is_sm true;}else (tmp[k] a[j]).is_sm false;}copy(tmpl,tmpr1,al);solve2(l,r);
}
int main(){
// freopen(partial_order.in,r,stdin);
// freopen(partial_order.out,w,stdout);read(n);for(int i1;in;i) read(a[i].a);for(int i1;in;i) read(a[i].b);for(int i1;in;i) read(a[i].c);solve1(1,n);printf(%d\n,ans);getchar();getchar();return 0;
} 转载于:https://www.cnblogs.com/Skyminer/p/6405323.html
