2018-8-10题解
目录：
- Sequence
- Graph
- Strange
Sequence
题意
期末考试结束了, 小C所在的班级要进行考试成绩的排名.
排名规则是这样的: 对于成绩为 $a_i$ 的同学, 他的排名等于成绩严格小于 $a_i$ 的同学的成绩 $a_j$ 组成的集合$\{a_j\}$的大小.
现在小C想知道, 如果有 $n$ 个人参加了考试, 一共有多少种可能的排名结果. 两种排名结果不同当且仅当至少有一个人在两次排名中排名不同.
输出对$1004535809$取膜
$n\le 10^5$
题解
这个膜数是个经典NTT膜数
设$f_{n,m}$表示n个人恰好m个分数段的方案，$Ans=\sum\limits_{i=1}^n f_{n,i}$。
容斥。枚举k个分数段一定没人。
$f_{n,m}=\sum\limits_{k=0}^m(-1)^k\binom{m}{k}(m-k)^n=m!\sum\limits_{k=0}^m\frac{(-1)^k}{k!} \cdot \frac{(m-k)^n}{(m-k)!}$。
就是两个指数生成函数的卷积.....
可以NTT计算$f_{n,1..n}$。
时间复杂度$O(n\log n)$。
Graph
题意
题解
Strange
题意
小S热爱大自然, 一天他种了一棵奇怪的线段树.
奇怪的线段树是一种与普通线段树类似的结构, 唯一不同的是, 它不一定以每一个区间的中点作为分治中心.
麻烦的是, 小S的线段树被风吹散了, 散成了一个个表示单一区间的结点, 而且正在逐渐飘远. 不过小S早有准备, 他可以进行抓取操作, 每一次他可以给出一个抓取区间, 由于这个抓取区间只有两个端点有磁力, 所以只能抓取满足与抓取区间有交而不被抓取区间包含的所有线段树结点.
现在小S进行了若干次抓取操作, 对于每次操作, 他希望你能回答他一共抓取了多少个线段树结点.
线段树长度$N\le 10^5$，操作次数$M\le 3\cdot10^6$。
题解
对于一个询问区间$L,R$，对于一个被抓取节点 它要么是叶子$L$的祖先 要么是叶子$R$的祖先 要么是它们共同的祖先。
倍增计算L不被询问区间包含的最近祖先A 和R不被询问包含的最近祖先B，设$Dis_A$表示A节点的深度。
那么答案就是$Dis_A+Dis_B-Dis_{lca(A,B)}$。
时间复杂度$O(m\log n)$，显然不能过。
计算LCA可以不用倍增 而是用欧拉序RMQ。
计算A,B的时候？把A的定义改成计算L祖先中深度最大的左端点<L的节点（也就是第一个是它父亲右儿子的节点） B的定义也类似，这样计算就可以$O(n)$预处理了。
这样就变成$O(n\log n)$预处理，$O(1)$询问了。
时间复杂度$O(n\log n+m)$。
/*
Author: CNYALI_LK
LANG: C++
PROG: strange.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#include<sys/mman.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
namespace input{
char* s;
int a[24];
void io(){s=(char*)mmap(NULL,1 << 26 ,PROT_READ,MAP_PRIVATE,fileno(stdin),0);}
void scan(char* u){
while(*s<48)
++s;
while(*s>32)
*u++=*s++;
*u=0;
}
int Read(){
int Hibiki=0,v=1;
while(*s<48)
v=*s++^45?1:-1;
while(*s>32)
Hibiki=Hibiki*10+*s++-48;
return Hibiki*v;
}
};
namespace output{
static const int BUF=50000000;
char buf[BUF],*h=buf;
inline void put(char ch){
h==buf+BUF?(fwrite(buf,1,BUF,stdout),h=buf):0;
*h++=ch;
}
inline void putint(int num){
static char _buf[30];
sprintf(_buf,"%d",num);
for (char *s=_buf;*s;s++)put(*s);
}
inline void finish(){
fwrite(buf,1,h-buf,stdout);
}
};
const int N=455555;
int dis[N],tt,rmq[20][N],leaf[N],lx[N],rx[N],t,cx[N],lg2[N];
void DFS(int l,int r,int f,int nrl,int nrr){
int s=++tt;
lx[s]=nrl;
rx[s]=nrr;
rmq[0][cx[s]=++t]=dis[s]=dis[f]+1;
if(l==r){
leaf[l]=s;
}
else{
int mid=input::Read();
DFS(l,mid,s,nrl,s);
rmq[0][++t]=dis[s];
DFS(mid+1,r,s,s,nrr);
rmq[0][++t]=dis[s];
}
}
int lca(int u,int v){
u=cx[u];v=cx[v];
if(u>v)swap(u,v);
int s=lg2[v-u+1];
return min(rmq[s][u],rmq[s][v-(1<<s)+1]);
}
int calc(int l,int r){
int u=lx[leaf[l]],v=rx[leaf[r]],s;
return dis[u]+dis[v]-lca(u,v);
}
int main(){
#ifdef cnyali_lk
freopen("strange.in","r",stdin);
freopen("strange.out","w",stdout);
#endif
int n,m,l,r;
input::io();
n=input::Read();
m=input::Read();
DFS(1,n,0,0,0);
for(int i=2;i<=t;++i)lg2[i]=lg2[i>>1]+1;
for(int i=1;i<=19;++i)for(int j=1;j+(1<<i)-1<=t;++j){
rmq[i][j]=min(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
}
for(;m;--m){
l=input::Read();r=input::Read();
output::putint(calc(l,r));
output::put('\n');
}
output::finish();
return 0;
}