\(\text{Knockout}\)
原题：\(\text{Boomerang Tournament}\)。
题目描述
有 \(n\) 支队伍（\(n\) 是 \(2^k\)）进行淘汰赛，已知两两胜负关系。在每种对阵情况中，请计算出第 \(i\) 支队伍的最好名次和最劣名次。
\(1\le T,n\le 16\)，\(G_{i,i}=0\)，对于所有 \(i\neq j\)，都有 \(G_{i,j}\neq G_{j,i}\)。
需要注意名次的计算方式。将所有队伍按胜出场数从大到小排序，比如有两队并列第三，那么 下一种 场数的队伍就应该是第五名。
\(\rm sb\) 博主观察了老久的样例都没看懂…
解法
很玄学的是，我随机化了 \(10^5\) 次就拿到了 \(\rm 100pts\)… 代码戳这。但是我算了算，本质不同的排列是 \(\frac{16!}{2^8\cdot 2^4\cdot 2^2 \cdot 2}\) 的？就很离谱。
令 \(dp_{s,i}\) 是在 \(s\) 的集合中，\(i\) 是否能成为优胜者，其中 \(s\) 一定是 \(2\) 的幂。转移是比较简单的，我主要是分析一下复杂度。
考虑有四个 \(1\) 的集合共有 \(\binom{16}{4}=1820\) 个，有八个 \(1\) 的集合共有 \(\binom{16}{8}=12870\) 个，其余的都比较小了，不妨只分析 \(siz=16,8\) 的循环。
这样大概是 \(\mathcal O((1\cdot 12870\cdot 8^2/2+12870\cdot \binom{8}{4}\cdot 4^2/2)\cdot T)\)，还是蛮稳的。
代码
#include <cstdio>
#define print(x,y) write(x),putchar(y)
template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while((s=getchar())>'9' or s<'0')
f|=(s=='-');
while(s>='0' and s<='9')
x=(x<<1)+(x<<3)+(s^48),
s=getchar();
return f?-x:x;
}
template <class T>
inline void write(const T x) {
if(x<0) {
putchar('-');
write(-x);
return;
}
if(x>9) write(x/10);
putchar(x%10^48);
}
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=20;
int n,g[maxn][maxn];
int dp[1<<16][17];
int mx[maxn],mn[maxn];
vector <int> mask[17];
void init() {
for(int i=0;i<(1<<16);++i) {
int t=__builtin_popcount(i);
if(((t-1)&t)==0)
mask[t].push_back(i);
}
}
int lowbit(int x) {
return x&-x;
}
int main() {
freopen("knock.in","r",stdin);
freopen("knock.out","w",stdout);
int fk=0;
init();
for(int T=read(9);T;--T) {
memset(dp,0,sizeof dp);
n=read(9);
for(int i=0;i<n;++i) {
mx[i]=0,mn[i]=n;
dp[1<<i][i]=1;
for(int j=0;j<n;++j)
g[i][j]=read(9);
}
printf("Case #%d:\n",++fk);
int dep=1;
for(int siz=2;siz<=n;siz<<=1,++dep)
for(int uu=0;uu<mask[siz].size();++uu) {
int U=mask[siz][uu];
if(U>=(1<<n)) break;
for(int ss=0;ss<mask[siz>>1].size();++ss) {
int S=mask[siz>>1][ss];
if((S&U)!=S) continue;
int T=U^S;
if(S>T) continue;
int s=S;
while(s) {
int i=__builtin_ctz(s);
s-=lowbit(s);
if(!dp[S][i]) continue;
int t=T;
while(t) {
int j=__builtin_ctz(t);
t-=lowbit(t);
if(!dp[T][j]) continue;
if(g[i][j]) {
dp[U][i]=1;
mx[i]=max(mx[i],dep);
mn[j]=min(mn[j],dep-1);
}
else {
dp[U][j]=1;
mx[j]=max(mx[j],dep);
mn[i]=min(mn[i],dep-1);
}
}
}
}
}
--dep;
for(int i=0;i<n;++i) {
int a=(mx[i]==dep)?0:(1<<(dep-mx[i]-1));
int b=(mn[i]>=dep)?0:(1<<(dep-mn[i]-1));
printf("%d %d\n",a+1,b+1);
}
}
return 0;
}
\(\text{[ZJOI 2012] }\)小蓝的好友
解法
首先转化成一条鱼都没有的矩形有多少个。
考虑添加一条与 \(x\) 轴平行的扫描线，从上往下移，那么扫描线以上的部分可以形成一个柱状图（遇见鱼 \((x,y)\) 后将经过 \(x\) 的柱高度置为 \(0\)）。
对于固定的柱状图，我们可以以 \(x\) 为 \(\rm key\)，高度为 \(\rm val\) 建立一棵笛卡尔树。对于每个宽为 \(w\)，长为 \(h\) 的完整矩形，内部矩形计算公式是 \(\frac{w(w+1)}{2}\cdot h\)（相当于最左边的 \(x\) 与 \(x,x+1,...,x+w-1\) 配对，依此类推）。单次计算是 \(\mathcal O(n)\) 的。
如何优化？考虑每次往下移扫描线，所有柱高度加一，遇到鱼时柱高度变为 \(0\)，而且还要维护笛卡尔树。用 \(\rm treap\) 啊！
当某个柱高度变为 \(0\) 时，\(\rm val\) 改变导致堆的条件不满足，所以需要 split() 一下。因为鱼是随机的，所以是 \(\mathcal O(n\log n)\) 的。
代码
#include <cstdio>
#define print(x,y) write(x),putchar(y)
template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while((s=getchar())>'9' or s<'0')
f|=(s=='-');
while(s>='0' and s<='9')
x=(x<<1)+(x<<3)+(s^48),
s=getchar();
return f?-x:x;
}
template <class T>
inline void write(const T x) {
if(x<0) {
putchar('-');
write(-x);
return;
}
if(x>9) write(x/10);
putchar(x%10^48);
}
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=100005;
ll S(int n) {
return 1ll*n*(n+1)/2;
}
int r,c,n;
struct fish {
int x,y;
bool operator < (const fish &t) const {
return y<t.y;
}
} s[maxn];
struct fhq_treap {
int idx,rt;
struct node {
int h,ls,rs,siz,la;
ll ans;
} t[maxn];
int NewNode(int H) {
t[++idx].siz=1;
t[idx].h=H;
return idx;
}
void add(int o,int k) {
if(!o) return;
t[o].la+=k;
t[o].h+=k;
}
void pushDown(int o) {
if(!o or !t[o].la)
return;
add(t[o].ls,t[o].la);
add(t[o].rs,t[o].la);
t[o].la=0;
}
void pushUp(int o) {
if(!o) return;
t[o].ans=0;
t[o].siz=t[t[o].ls].siz+t[t[o].rs].siz+1;
if(t[o].ls)
t[o].ans+=t[t[o].ls].ans+S(t[t[o].ls].siz)*(t[t[o].ls].h-t[o].h);
if(t[o].rs)
t[o].ans+=t[t[o].rs].ans+S(t[t[o].rs].siz)*(t[t[o].rs].h-t[o].h);
}
void split(int o,int k,int &x,int &y) {
if(!o) x=y=0;
else {
pushDown(o);
if(t[t[o].ls].siz+1<=k) {
x=o;
split(t[o].rs,k-t[t[o].ls].siz-1,t[o].rs,y);
}
else {
y=o;
split(t[o].ls,k,x,t[o].ls);
}
pushUp(o);
}
}
int merge(int x,int y) {
if(!x or !y)
return x|y;
if(t[x].h<t[y].h) {
pushDown(x);
t[x].rs=merge(t[x].rs,y);
pushUp(x);
return x;
}
else {
pushDown(y);
t[y].ls=merge(x,t[y].ls);
pushUp(y);
return y;
}
}
void build(int n) {
for(int i=1;i<=n;++i)
rt=merge(rt,NewNode(0));
}
} T;
int main() {
r=read(9),c=read(9),n=read(9);
for(int i=1;i<=n;++i)
s[i]=(fish){read(9),read(9)};
T.build(r);
sort(s+1,s+n+1);
ll ans=S(r)*S(c);
int pos=1;
for(int i=1;i<=c;++i) {
T.add(T.rt,1);
while(pos<=n and s[pos].y==i) {
int cut=s[pos].x,a,b,c;
T.split(T.rt,cut-1,a,b);
T.split(b,1,b,c);
T.t[b].h=0;
T.rt=T.merge(T.merge(a,b),c);
++pos;
}
ans-=T.t[T.rt].ans+S(T.t[T.rt].siz)*T.t[T.rt].h;
// 最后还要计算最下面完整的一块
}
print(ans,'\n');
return 0;
}