因为之前忘做了，赶紧补上。
T1.Promotion Counting
题目大意：给定一个以1为根的N个节点的树（N<=100,000），每个节点有一个权值，对于每个节点求出权值比它大的子孙的个数。
思路：肯定先要求出dfs序，首先无脑想到主席树，后来发现只要按权值从大到小处理就不用那么麻烦了。
#include<cstdio>
#include<algorithm>
using namespace std;
char B[<<],*S=B,C;int X;
inline int read()
{
while((C=*S++)<''||C>'');
for(X=C-'';(C=*S++)>=''&&C<='';)X=(X<<)+(X<<)+C-'';
return X;
}
#define MN 100000
#define lb(x) (x&-x)
struct edge{int nx,t;}e[MN+],p[MN+];
int h[MN+],en,d[MN+],o[MN+],cnt,s[MN+],ans[MN+];
bool cmp(edge a,edge b){return a.t>b.t;}
inline void ins(int x,int y){e[++en]=(edge){h[x],y};h[x]=en;}
void pre(int x)
{
d[x]=++cnt;
for(int i=h[x];i;i=e[i].nx)pre(e[i].t);
o[x]=cnt;
}
inline void inc(int x){for(;x<=MN;x+=lb(x))++s[x];}
inline int sum(int x){int r=;for(;x;x-=lb(x))r+=s[x];return r;}
int main()
{
fread(B,,<<,stdin);
int n=read(),i;
for(i=;i<=n;++i)p[i]=(edge){i,read()};
sort(p+,p+n+,cmp);
for(i=;i<=n;++i)ins(read(),i);
pre();
for(i=;i<=n;++i)
{
ans[p[i].nx]=sum(o[p[i].nx])-sum(d[p[i].nx]);
inc(d[p[i].nx]);
}
for(i=;i<=n;++i)printf("%d\n",ans[i]);
}
T2.Building a Tall Barn
题目大意：给定长度为N的序列ai，对每个ai分配ci使得ci>0且ci之和等于K，求出最小的ai/ci之和。（N<=100,000，K<=10^12）
思路：容易想到先给每个ai分1，用堆维护每个ai再多分1能获得的收益，O(KlogN)实现。也就相当于N堆物品，从中取走K个求最大收益，我们二分一个取的下界，把大于这个下界的都取走，看看取了几个就可以了，取几个我一开始也二分，T了，然后发现可以数学直接算。另外这题精度要求可能比较大，二分多分几次就行了，最后O(NlogK)。从题解中学到了种二分写法（虽然好像以前见识过）：for(i=1;i<=100;++i)if(check(mid))...
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
#define ll long long
char B[<<],*S=B,C;ll X;
inline ll read()
{
while((C=*S++)<''||C>'');
for(X=C-'';(C=*S++)>=''&&C<='';)X=(X<<)+(X<<)+C-'';
return X;
}
#define MN 100000
ll k,a[MN+];
ll cal(double x){return (ll)((sqrt(+*x)-)/);}
int main()
{
fread(B,,<<,stdin);
int n=read(),i;k=read()-n;double l,r,mid;ll cnt;
for(i=;i<=n;++i)a[i]=read();
for(l=,r=1e12;r-l>1e-;)
{
mid=(l+r)/;
for(cnt=,i=;i<=n;++i)cnt+=cal(a[i]/mid);
if(cnt<=k)r=mid;else l=mid;
}
for(i=,l=;i<=n;++i)l+=a[i]/(double)(cal(a[i]/r)+);
cout<<(ll)(l+0.5);
}
T3.Subsequence Reversal
题目大意：给定一个长度为N的序列，允许翻转一个子序列，求最长不下降子序列长度。（N<=50，序列元素在1..50内）
思路：一眼看上去很不可做，而且N这么小很吓人，仔细想想可以搞个类似区间DP，从整个序列开始，左边一个元素不翻或右边一个元素不翻或交换这两个元素（交换可能两个都选入答案也可能只选一个，转移时都要考虑），逐渐把区间缩小，然后再在状态里加上能取的数字区间，还是挺好转移的，复杂度O(N^2*maxai^2)，另外题目里明明写的increasing却是不下降，很坑爹啊。
#include<cstdio>
#include<algorithm>
using namespace std;
char B[<<],*S=B,C;int X;
inline int read()
{
while((C=*S++)<''||C>'');
for(X=C-'';(C=*S++)>=''&&C<='';)X=(X<<)+(X<<)+C-'';
return X;
}
#define MN 50
int a[MN+],f[MN+][MN+][MN+][MN+],ans;
inline void r(int&a,int b){if(b>a){a=b;if(b>ans)ans=b;}}
int main()
{
fread(B,,<<,stdin);
int n=read(),i,j,k,l;
for(i=;i<=n;++i)a[i]=read();
for(i=;i<=n;++i)for(j=n;j>=i;--j)
for(k=;k<=MN;++k)for(l=MN;l>=k;--l)
{
if(k<=a[i]&&a[i]<=l)
r(f[i+][j][a[i]][l],f[i][j][k][l]+),
r(f[i+][j-][k][a[i]],f[i][j][k][l]+);
if(k<=a[j]&&a[j]<=l)
r(f[i][j-][k][a[j]],f[i][j][k][l]+),
r(f[i+][j-][a[j]][l],f[i][j][k][l]+);
if(i<j&&k<=a[j]&&a[j]<=a[i]&&a[i]<=l)
r(f[i+][j-][a[j]][a[i]],f[i][j][k][l]+);
r(f[i+][j][k][l],f[i][j][k][l]);
r(f[i][j-][k][l],f[i][j][k][l]);
r(f[i][j][k+][l],f[i][j][k][l]);
r(f[i][j][k][l-],f[i][j][k][l]);
}
printf("%d",ans);
}