T1
Description
给定一个序列，初始为空。依次将$1-n$插入序列，其中$i$插到当前第$a_i$个数的右边($a_i=0$表示插到序列最左边)。求最终序列。
Input
第一行一个整数$n$。第二行$n$个正整数$a_1-a_n$。
Output
输出一行$n$个整数表示最终序列，数与数之间用一个空格隔开。
Sample Input
5
0 1 1 0 3
Sample Output
4 1 3 5 2
HINT
$n<=10^6,0;leq;a_i<i$.
Solution
首先，看到这种题显然倒着处理比较容易。
其次，这题$O(nlogn)$能过（可是我的机子跑不过啊！！！）
所以可以用线段树维护当前区间剩余可填格子的个数，每次寻找第$a[i]+1$个空格在哪。
#include<cmath> #include<ctime> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 5000005 using namespace std; struct linetree{ int l,r,s,b; }lt[N]; int a[N],s[N],ans[N],n; inline int read(){ int ret=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)){ ret=ret*10+c-'0'; c=getchar(); } return ret; } inline void build(int u,int l,int r){ lt[u].l=l;lt[u].r=r;lt[u].s=r-l+1; if(l==r) return; int lef=u<<1,rig;rig=lef|1; int mid=(l+r)>>1; build(lef,l,mid);build(rig,mid+1,r); } inline int ask(int u,int k){ if(lt[u].l==lt[u].r) return lt[u].l; int l=u<<1,r;r=l|1; if(lt[u].s==k) if(lt[l].s==k) ask(l,k); else ask(r,k-lt[l].s); else if(lt[l].s>=k) ask(l,k); else ask(r,k-lt[l].s); } inline bool chk(linetree l,int x){ return l.l<=x&&l.r>=x; } inline void dec(int u,int x){ if(chk(lt[u],x)) lt[u].s--; if(lt[u].l<lt[u].r){ int l=u<<1,r;r=l|1; if(chk(lt[l],x)) dec(l,x); else if(chk(lt[r],x)) dec(r,x); } else lt[u].b=true; } inline void init(){ n=read();build(1,1,n); for(int i=1;i<=n;i++) a[i]=read(); for(int i=n,k;i;i--){ k=ask(1,a[i]+1); ans[k]=i;dec(1,k); } for(int i=1;i<=n;i++) printf("%d ",ans[i]); printf(" "); } int main(){ freopen("sequence.in","r",stdin); freopen("sequence.out","w",stdout); init(); fclose(stdin); fclose(stdout); return 0; }
T2
Description
有$n$个物品和一个大小为$m$的背包，每个物品有大小和价值，求背包里最多能放下多少价值的物品。
Input
第一行两个整数$n,m$。接下来$n$行每行两个整数$x_i,w_i$，表示第$i$个物品的大小和价值。
Output
一行一个整数表示最大价值。
Sample Input
5 100
95 80
4 18
3 11
99 100
2 10
Sample Output
101
HINT
$n;leq;40,0;leq;m;leq;10^{18},0;leq;x_i,w_i;leq;10^{15}$.
Solution
显然数据不适合$dp$,由于$n$比较小，所以会想到折半搜索。
把前$n/2$个物品的所有方案存下来，删去明显劣的。
再枚举剩余的物品，对于每种方案，二分求与前$n/2$个物品能组成的最大价值。
（我以前有做过类似的题，只不过求的是是否存在总价值为$w$的方案，然而这题当时我还没想出来$QAQ$）
#include<cmath> #include<ctime> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 45 #define M 2000000 using namespace std; typedef long long ll; struct thing{ ll x,w; }a[N],b[M]; int n,nn,cnt=-1,tot=1; ll m,ans; inline ll search(ll m){ if(m<b[1].x) return 0; int l=1,r=tot,mid; while(l<r){ mid=l+r+1>>1; if(b[mid].x<=m) l=mid; else r=mid-1; } return b[l].w; } inline void dfs1(int u,ll sw,ll sx){ if(u>nn){ b[++cnt]=(thing){sx,sw}; return; } dfs1(u+1,sw,sx); if(sx+a[u].x<=m) dfs1(u+1,sw+a[u].w,sx+a[u].x); } inline void dfs2(int u,ll sw,ll sx){ if(u>n){ sw+=search(m-sx); ans=max(ans,sw); return; } dfs2(u+1,sw,sx); if(sx+a[u].x<=m) dfs2(u+1,sw+a[u].w,sx+a[u].x); } inline bool cmp(thing x,thing y){ if(x.x!=y.x) return x.x<y.x; return x.w>y.w; } inline void init(){ scanf("%d%lld",&n,&m); for(int i=1;i<=n;++i) scanf("%lld%lld",&a[i].x,&a[i].w); nn=n>>1;dfs1(1,0,0); sort(b+1,b+1+cnt,cmp); for(int i=2;i<=cnt;i++) if(b[i].x>b[i-1].x) b[++tot]=b[i]; for(int i=2;i<=tot;i++) b[i].w=max(b[i].w,b[i-1].w); dfs2(nn+1,0,0); printf("%lld ",ans); } int main(){ freopen("pack.in","r",stdin); freopen("pack.out","w",stdout); init(); fclose(stdin); fclose(stdout); return 0; }
T3
Description
有一棵线段树，根为$[1,n]$，有所不同的是，每个节点$[l,r]$的孩子为$[l,k]$,$[k+1,r]$，其中$l;leq;k<r$且$k$的值由你决定。给定$m$个区间，定义区间$[a_i,b_i]$会访问到节点$[l,r]$仅当他们会相交。求每次访问的结点个数之和的最小值。
Input
第一行两个整数$n,m$，接下来$m$行每行两个整数$a_i,b_i$。
Output
一行一个整数表示答案。
Sample Input
6 6
1 4
2 6
3 4
3 5
2 3
5 6
Sample Output
40
HINT
$n;leq;5000，m;leq;10^5$
Solution
$f[i][j]$表示节点$[i,j]$的子树中被访问的最少次数，$s[i][j]$表示与节点$[i,j]$相交的区间数。
$f[i][j]=min{f[i][k]+f[k+1][j]}+s[i][j];(i;leq;k<j)$。
直接枚举是$O(n^3)$,显然会$T$。
用四边形不等式优化能压到$O(n^2)$.
以下为不保证正确性的证明，不喜请跳过
①当$a;leq;b<c;leq;d$时，易证$s[a][c]+s[b][d]=s[b][c]+s[a][d]$，$s[;][;]$满足四边形不等式。
②当$[i,j]$属于$[i',j']$时，$s[i,j];leq;s[i',j'],s[;][;]$满足区间包含关系单调。
因为同时满足①②，所以$f[;][;]$满足四边形不等式。
记使$f[i][j]$取最小值时的$k$为$g[i][j]$,则$g[i][j-1];leq;g[i][j];leq;g[i+1][j]$。
易证枚举$k$的总时间复杂度为$O(n)$。
#include<cmath> #include<ctime> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 5005 #define M 10005 #define INF 500000005 using namespace std; int f[N][N],g[N][N],s[N][N],n,m; inline int read(){ int ret=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)){ ret=ret*10+c-'0'; c=getchar(); } return ret; } inline void init(){ n=read();m=read(); for(int i=1,j,k;i<=m;++i){ j=read();k=read(); ++s[k][j]; } for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) s[i][j]+=s[i][j-1]; for(int i=n;i;--i) for(int j=1;j<=n;++j) s[i][j]+=s[i+1][j]; for(int i=1;i<=n;++i){ f[i][i]=s[i][i]; g[i][i]=i; } for(int l=1;l<n;++l){ for(int i=1,j;i+l<=n;++i){ j=i+l;f[i][j]=INF; for(int k=g[i][j-1];k<=g[i+1][j];++k){ if(f[i][k]+f[k+1][j]<f[i][j]){ f[i][j]=f[i][k]+f[k+1][j]; g[i][j]=k; } } f[i][j]+=s[i][j]; } } printf("%d ",f[1][n]); } int main(){ freopen("segment.in","r",stdin); freopen("segment.out","w",stdout); init(); fclose(stdin); fclose(stdout); return 0; }