BZOJ2253: [2010 Beijing wc]纸箱堆叠

题解：

其实就是求三维偏序最长链。类似于三维逆序对，我们可以用树状数组套平衡树来实现。

DP方程：f[i]=max(f[j]+1) a[j]<a[i]

我们按一维排序，另一位建立树状数组，把第三维插入到每个树状数组的节点里。

除了权值之外每个节点还要保持一个mx，表示该子树内最大的f[i]。

这样就可以nlg^n了

UPD:试了下不带旋转的treap果然会被卡 orz

代码：

  1 #include<cstdio>
  2 
  3 #include<cstdlib>
  4 
  5 #include<cmath>
  6 
  7 #include<cstring>
  8 
  9 #include<algorithm>
 10 
 11 #include<iostream>
 12 
 13 #include<vector>
 14 
 15 #include<map>
 16 
 17 #include<set>
 18 
 19 #include<queue>
 20 
 21 #include<string>
 22 
 23 #define inf 1000000000
 24 
 25 #define maxn 150000+5
 26 
 27 #define maxm 4000000+5
 28 
 29 #define eps 1e-10
 30 
 31 #define ll long long
 32 
 33 #define pa pair<int,int>
 34 
 35 #define for0(i,n) for(int i=0;i<=(n);i++)
 36 
 37 #define for1(i,n) for(int i=1;i<=(n);i++)
 38 
 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
 40 
 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
 42 
 43 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)
 44 
 45 #define for5(n,m) for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
 46 
 47 #define mod 1000000007
 48 
 49 using namespace std;
 50 
 51 inline ll read()
 52 
 53 {
 54 
 55     ll x=0,f=1;char ch=getchar();
 56 
 57     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 58 
 59     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
 60 
 61     return x*f;
 62 
 63 }
 64 int n,tot,cnt,b[maxn],f[maxn],rt[maxn],c[maxn],d[maxn];
 65 int h[maxm],mx[maxm],l[maxm],r[maxm],v[maxm],vv[maxm];
 66 struct rec{int x,y,z;}a[maxn];
 67 bool operator <(rec a,rec b){return a.x<b.x;}
 68 inline void pushup(int k)
 69 {
 70     mx[k]=max(vv[k],max(mx[l[k]],mx[r[k]]));
 71 }
 72 inline void lturn(int &k)
 73 {
 74     int t=r[k];r[k]=l[t];l[t]=k;pushup(k);pushup(t);k=t;
 75 }
 76 inline void rturn(int &k)
 77 {
 78     int t=l[k];l[k]=r[t];r[t]=k;pushup(k);pushup(t);k=t;
 79 }
 80 inline void insert(int &k,int x,int y)
 81 {
 82     if(!k)
 83     {
 84         k=++tot;v[k]=x;h[k]=rand();vv[k]=mx[k]=y;
 85         return;
 86     }
 87     if(x==v[k])vv[k]=max(vv[k],y);
 88     else if(x<v[k]){insert(l[k],x,y);if(h[k]<h[l[k]])rturn(k);}
 89     else {insert(r[k],x,y);if(h[k]<h[r[k]])lturn(k);}
 90     pushup(k);
 91 }
 92 inline int getmx(int k,int x)
 93 {
 94     if(!k)return 0;
 95     if(v[k]==x)return max(mx[l[k]],vv[k]);
 96     else if(x<v[k])return getmx(l[k],x);
 97     else return max(max(mx[l[k]],vv[k]),getmx(r[k],x));
 98 }
 99 inline int query(int x,int y)
100 {
101     int ret=0;
102     for(;x;x-=x&(-x)){ret=max(ret,getmx(rt[x],y));}
103     return ret;
104 }
105 inline void add(int x,int y,int z)
106 {
107     for(;x<=cnt;x+=x&(-x))insert(rt[x],y,z);
108 }
109 inline bool cmp(int x,int y){return b[x]<b[y];}
110 
111 int main()
112 
113 {
114 
115     freopen("input.txt","r",stdin);
116 
117     freopen("output.txt","w",stdout);
118 
119     ll t=read(),p=read();n=read();b[0]=1;
120     for1(i,3*n)b[i]=(ll)b[i-1]*t%p,c[i]=i;
121     sort(c+1,c+3*n+1,cmp);
122     cnt=0;
123     for1(i,3*n)
124     {
125         if(i==1||b[c[i]]!=b[c[i-1]])cnt++;
126         d[c[i]]=cnt;
127     }
128     for1(i,n)a[i].x=d[3*i-2],a[i].y=d[3*i-1],a[i].z=d[3*i];
129     for1(i,n)
130     {
131         if(a[i].y>a[i].x)swap(a[i].x,a[i].y);
132         if(a[i].z>a[i].x)swap(a[i].x,a[i].z);
133         if(a[i].z>a[i].y)swap(a[i].z,a[i].y);
134     }
135     sort(a+1,a+n+1);
136     for(int l=1,r=1;l<=n;r++,l=r)
137     {
138         while(a[r+1].x==a[l].x)r++;
139         for2(i,l,r)f[i]=query(a[i].y-1,a[i].z-1)+1;//cout<<i<<' '<<f[i]<<endl;
140         for2(i,l,r)add(a[i].y,a[i].z,f[i]);
141     }
142     int ans=0;
143     for1(i,n)ans=max(ans,f[i]);
144     cout<<ans<<endl;
145 
146     return 0;
147 
148 }

View Code

2253: [2010 Beijing wc]纸箱堆叠

Time Limit: 30 Sec Memory Limit: 256 MB
Submit: 246 Solved: 96
[Submit][Status]

Description

P 工厂是一个生产纸箱的工厂。纸箱生产线在人工输入三个参数 n p a , , 之后，
即可自动化生产三边边长为

(a mod P,a^2 mod p,a^3 mod P)
(a^4 mod p,a^5 mod p,a^6 mod P)
....
(a^(3n-2) mod p,a^(3n-1) mod p,a^(3n) mod p)

的n个纸箱。在运输这些纸箱时，为了节约空间，必须将它们嵌套堆叠起来。
一个纸箱可以嵌套堆叠进另一个纸箱当且仅当它的最短边、次短边和最长边
长度分别严格小于另一个纸箱的最短边、次短边和最长边长度。这里不考虑
任何旋转后在对角线方向的嵌套堆叠。
你的任务是找出这n个纸箱中数量最多的一个子集，使得它们两两之间都可
嵌套堆叠起来。

Input

输入文件的第一行三个整数，分别代表 a,p,n

Output

输出文件仅包含一个整数，代表数量最多的可嵌套堆叠起来的纸箱的个数。

Sample Input

10 17 4

Sample Output

2
【样例说明】
生产出的纸箱的三边长为(10, 15, 14), (4, 6, 9) , (5, 16, 7), (2, 3, 13)。其中只有
(4, 6, 9)可堆叠进(5, 16, 7)，故答案为 2。
2<=P<=2000000000,1<=a<=p-1,a^k mod p<>0,ap<=2000000000,1<=N<=50000

秒客网