A.三维偏序问题
题意
给你 (n) 个三元组 ((x_i,y_i,z_i)) ，求对于每一个 ((x_i,y_i,z_i)) ， (x_j<x_i,y_j<y_i,z_j<z_i) 的个数。 ((nle 100000))
解
对于一维偏序，直接排序。
对于二维偏序，先排序排掉一维 (x) ，再对另一维 (y) 用树状数组或归并排序维护。（做法同“求逆序对”）
对于三维偏序，先排序排掉一维 (x) ，然后考虑分治，先处理区间 ([l,mid],[mid+1,r]) ，保持 (y) 有序，然后归并 (x) ，同时用树状数组维护第三维 (z) 。
对于更高维的偏序，理论上是可行的，每次复杂度加一个 (log) 。
Template Code
#include<cstdio>
#include<algorithm>
#define maxn 100003
#define maxv 100000
using namespace std;
template<typename tp>
void read(tp& x){
x=0;
char c=getchar();
bool sgn=0;
while((c<'0'||c>'9')&&c!='-')c=getchar();
if(c=='-')sgn=1,c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
if(sgn)x=-x;
}
template<typename tp>
void write(tp x){
if(x<0)putchar('-'),write(-x);
else{
if(x>=10)write(x/10);
putchar(x%10+'0');
}
}
struct T{
int a,b,c,num;
bool operator ==(const T& x){return a==x.a&&b==x.b&&c==x.c;}
}a[maxn];
int n,rig[maxn],t[maxn],ANS[maxn];
bool cmp(const T& x,const T& y){return x.a!=y.a?x.a<y.a:(x.b!=y.b?x.b<y.b:x.c<y.c);}
bool cmp1(const T& x,const T& y){return x.b!=y.b?x.b<y.b:(x.c!=y.c?x.c<y.c:x.a<y.a);}
void add(int pos,int k){
while(pos<=maxv)t[pos]+=k,pos+=pos&-pos;
}
int query(int pos){
int ret=0;
while(pos)ret+=t[pos],pos-=pos&-pos;
return ret;
}
void cdq(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
cdq(l,mid),cdq(mid+1,r);
sort(a+l,a+r+1,cmp1);
for(int i=l;i<=r;i++){
if(a[i].a<=mid)add(a[i].c,1);
else ANS[a[i].num]+=query(a[i].c);
}
for(int i=l;i<=r;i++){
if(a[i].a<=mid)add(a[i].c,-1);
}
}
int main(){
int T;
read(T);
while(T--){
read(n);
for(int i=1;i<=n;i++)ANS[i]=0;
for(int i=1;i<=n;i++){
read(a[i].a),read(a[i].b),read(a[i].c);
a[i].num=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1,j=1;i<=n;){
while(j<=n&&a[j]==a[i]){
j++;
}
while(i<j){
rig[a[i].num]=a[j-1].num;
i++;
}
}
for(int i=1;i<=n;i++)a[i].a=i;
cdq(1,n);
for(int i=1;i<=n;i++)write(ANS[rig[i]]),putchar('
');
}
return 0;
}
B.
题意
有 (n) 个在三维空间中的球，一个球 (i) 能击中另一个 (j) 的条件是 (x_i<x_j,y_i<y_j,z_i<z_j) 。现在你能够打出某一个球，问最多有几个球能被击中，并输出击中最多个数的球的方案数。((nle 100000))
解
利用cdq中的树状数组维护最值来转移dp。每个dp状态最好写一个结构体。
注意：与cdq模板题不同，必须先递归左区间，再dp，再递归右区间。
Code
#include<cstdio>
#include<algorithm>
#define maxn 100003
#define mod 1073741824
using namespace std;
template<typename tp>
void read(tp& x){
x=0;
char c=getchar();
bool sgn=0;
while((c<'0'||c>'9')&&c!='-')c=getchar();
if(c=='-')sgn=1,c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
if(sgn)x=-x;
}
template<typename tp>
void write(tp x){
if(x<0)putchar('-'),write(-x);
else{
if(x>=10)write(x/10);
putchar(x%10+'0');
}
}
struct T{
int a,b,c,num;
bool operator ==(const T& x){return a==x.a&&b==x.b&&c==x.c;}
}a[maxn],b[maxn];
int n,mp[maxn],cntmp;
bool cmp(const T& x,const T& y){return x.a!=y.a?x.a<y.a:(x.b!=y.b?x.b<y.b:x.c<y.c);}
bool cmp1(const T& x,const T& y){return x.b!=y.b?x.b<y.b:(x.c!=y.c?x.c<y.c:x.a<y.a);}
int Plus(int x,int y){return (x+=y)>=mod?x%mod:x;}
struct P{
int len,cnt;
P():len(0),cnt(0){}
P(int _l,int _c):len(_l),cnt(_c){}
}t[maxn],dp[maxn];
void pushup(P& x,const P& y){
if(x.len<y.len)x=y;
else if(x.len==y.len)x.cnt=Plus(x.cnt,y.cnt);
}
void add(int pos,const P& k){
while(pos<=cntmp)pushup(t[pos],k),pos+=pos&-pos;
}
void del(int pos){
while(pos<=cntmp)t[pos]=P(),pos+=pos&-pos;
}
P query(int pos){
P ret;
while(pos)pushup(ret,t[pos]),pos-=pos&-pos;
return ret;
}
void cdq(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
cdq(l,mid);
for(int i=l;i<=r;i++){
b[i]=a[i];
}
sort(b+l,b+r+1,cmp1);
for(int i=l;i<=r;i++){
if(b[i].a<=mid){
add(b[i].c,dp[b[i].num]);
}
else{
P tmp=query(b[i].c);
tmp.len++;
pushup(dp[b[i].num],tmp);
}
}
for(int i=l;i<=r;i++){
if(b[i].a<=mid){
del(b[i].c);
}
}
cdq(mid+1,r);
}
int main(){
int T;
read(T);
while(T--){
read(n);
for(int i=1;i<=n;i++)dp[i]=P(1,1);
cntmp=0;
for(int i=1;i<=n;i++){
read(a[i].a),read(a[i].b),read(a[i].c);
mp[++cntmp]=a[i].c;
a[i].num=i;
}
sort(mp+1,mp+cntmp+1);
cntmp=unique(mp+1,mp+cntmp+1)-mp-1;
for(int i=1;i<=n;i++){
a[i].c=lower_bound(mp+1,mp+cntmp+1,a[i].c)-mp;
}
sort(a+1,a+n+1,cmp);tiyi
for(int i=1;i<=n;i++)a[i].a=i;
cdq(1,n);
P ans;
for(int i=1;i<=n;i++)pushup(ans,dp[i]);
write(ans.len),putchar(' '),write(ans.cnt),putchar('
');
}
return 0;
}
C.
题意
给定一个 (N*N) 的网格，现有 (M) 组操作，一种操作时改变网格上的某一个点的权值，另外一种操作是求到一点曼哈顿距离为小于等于 (k) 的所有的权值和，初始化网格所有点的权值为 (0) 。((N,Mle 10^5))
解
首先想到将坐标旋转 (45°) ，将曼哈顿距离转化。本来所有点构成的图形是一个菱形，转一下之后就变成了正方形，然后就转化为一个二维数点问题，可以使用二维树状数组或者cdq维护。
下面讲一讲cdq做法。
我们把当前问题转化为三维偏序问题： ((t,x,y)) 表示坐标为 ((x,y)) 的点在 (t) 时刻修改操作或者询问操作，统计每个询问操作的答案。
询问操作需要拆成4个询问点，然后用容斥原理减一减。
D.动态逆序对
题意
求一个序列的动态逆序对（带修改）。
解
将问题转化为三维偏序问题： ((t,x,v)) 表示 (t) 时刻位置 (x) 的点变成了 (v) 。
然后做法就如出一辙。
F.
题意
解
存一个结构体，保存当前值在序列中的位置、更改前的值、更改后与更改前的值的 (min) 、更改后与更改前的值的 (max) 。
那么，元素 (i) 能作为元素 (j) 的后继的条件为： (j) 更改前的值 (<i) 的 (min) 且 (j) 的 (max <i) 更改前的值。
然后对位置分治，保持左半边的 (max) 有序，右半边更改前的值有序，然后dp。