[BZOJ 2599][IOI2011]Race
由于一些琐事，很长时间没有更新博客了……尽管做了不少题，但还是给我些时间整理思绪吧……
大方向肯定是点分治没错啦……
点分治的题处理经过根的路径通常有两种套路……一种是类似BZOJ 1468那样，收集所有儿子的信息，然后一次性合并，并排除不合法的情况。另一种类似于这道题，顺次处理儿子的信息，处理一个合并一个。
具体的思路是，用[tex]p[x][/tex]表示目前已知的所有从根开始长度为[tex]x[/tex]的路径（当然根本身也算上啦，所以说一开始就把[tex]p[root][/tex]设为0），然后根搜集信息时每次对一个儿子进行DFS，假设某结点[tex]x[/tex]到根的距离为[tex]d[x][/tex]，那么显然[tex]x[/tex]对答案的贡献为[tex]p[k-d[x]][/tex]，之后把这个子树合并到[tex]p[/tex]中。
注意清理[tex]p[/tex]的时候不能直接暴力memset……这样会被卡常致死。更好的方法是对于每次把子树合并到[tex]p[/tex]中时，把[tex]x[/tex]记录下来，然后清理[tex]p[/tex]时常数就小很多了。
代码：
/**************************************************************
Problem: 2599
User: danihao123
Language: C++
Result: Accepted
Time:14640 ms
Memory:23532 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn = 200005;
const int maxm = maxn * 2;
const int maxk = 1000005;
struct Edge {
Edge *next;
int to, dist;
};
Edge pool[maxm];
int graph_cnt;
Edge *first[maxn];
inline void clear_graph() {
graph_cnt = 0;
memset(first, 0, sizeof first);
}
inline void add_edge(int u, int v, int d) {
Edge *e = &pool[graph_cnt++];
e->next = first[u];
first[u] = e;
e->to = v;
e->dist = d;
}
int k;
bool vis[maxn];
int siz[maxn];
void gen_siz(int x, int fa) {
siz[x] = 1;
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(!vis[v] && v != fa) {
gen_siz(v, x);
siz[x] += siz[v];
}
}
}
int now_root, best_root;
void gen_best_root(int x, int fa) {
bool OK = siz[x]*2 >= siz[now_root];
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(!vis[v] && v != fa) {
gen_best_root(v, x);
OK = OK && (siz[v]*2 <= siz[now_root]);
}
}
if(OK) {
best_root = x;
}
}
int buf[maxk];
int ans;
void deal_ans(int x, int fa, int dep, int d) {
if(d > k) {
return;
}
ans = min(ans, dep + buf[k-d]);
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(!vis[v] && v != fa) {
deal_ans(v, x, dep + 1, d + e->dist);
}
}
}
void add_to_buf(int x, int fa, int dep, int d) {
if(d > k) {
return;
}
buf[d] = min(buf[d], dep);
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(!vis[v] && v != fa) {
add_to_buf(v, x, dep + 1, d + e->dist);
}
}
}
void clear_buf(int x, int fa, int dep, int d) {
if(d > k) {
return;
}
buf[d] = 0x3f3f3f3f;
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(!vis[v] && v != fa) {
clear_buf(v, x, dep + 1, d + e->dist);
}
}
}
void divide(int x) {
gen_siz(x, 0);
now_root = best_root = x; gen_best_root(x, 0);
x = best_root;
vis[x] = true;
buf[0] = 0;
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(!vis[v]) {
deal_ans(v, x, 1, e->dist);
add_to_buf(v, x, 1, e->dist);
}
}
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(!vis[v]) {
clear_buf(v, x, 1, e->dist);
}
}
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(!vis[v]) {
divide(v);
}
}
}
inline int readint() {
int x = 0;
char c = getchar();
while(!isdigit(c)) {
c = getchar();
}
while(isdigit(c)) {
x = x * 10 + (c - '0');
c = getchar();
}
return x;
}
int main() {
int n;
n = readint();
k = readint();
clear_graph();
for(int i = 1; i <= (n-1); i++) {
int u, v, d;
u = readint();
v = readint();
d = readint();
u++; v++;
add_edge(u, v, d);
add_edge(v, u, d);
}
ans = 0x3f3f3f3f;
memset(buf, 0x3f, sizeof buf);
divide(1);
if(ans == 0x3f3f3f3f) {
ans = -1;
}
printf("%d\n", ans);
return 0;
}
[BZOJ 1086][SCOI2005]王室联邦
最近想捉一下树分块，这道题肯定是要做的啦~
这个题的方法就是蜜汁贪心，在其他树分块的题目中也有应用。
代码：
/**************************************************************
Problem: 1086
User: danihao123
Language: C++
Result: Accepted
Time:16 ms
Memory:880 kb
****************************************************************/
#include <cstdio>
#include <stack>
using std::stack;
const int maxn=1005;
const int maxm=maxn*2;
int first[maxn];
int next[maxm],to[maxm];
int graph_cnt=0;
inline void AddEdge(int u,int v){
graph_cnt++;
next[graph_cnt]=first[u];
first[u]=graph_cnt;
to[graph_cnt]=v;
}
int belong[maxn],cap[maxn];
int block_cnt=0;
stack<int> S;
int B;
void DFS(int u,int fa){
int siz=S.size();
for(int i=first[u];i;i=next[i]){
int v=to[i];
if(v==fa){
continue;
}
DFS(v,u);
if((S.size()-siz)>=B){
block_cnt++;
cap[block_cnt]=u;
while(S.size()>siz){
int x=S.top();S.pop();
belong[x]=block_cnt;
}
}
}
S.push(u);
}
int main(){
register int i;
bool OK;
int n,u,v;
scanf("%d%d",&n,&B);
for(i=1;i<=(n-1);i++){
scanf("%d%d",&u,&v);
AddEdge(u,v);
AddEdge(v,u);
}
if(n<B){
puts("0");
return 0;
}
DFS(1,0);
while(!S.empty()){
int x=S.top();S.pop();
belong[x]=block_cnt;
}
printf("%d\n",block_cnt);
OK=false;
for(i=1;i<=n;i++){
if(OK){
putchar(' ');
}
OK=true;
printf("%d",belong[i]);
}
putchar('\n');
OK=false;
for(i=1;i<=block_cnt;i++){
if(OK){
putchar(' ');
}
OK=true;
printf("%d",cap[i]);
}
putchar('\n');
return 0;
}
[BZOJ 1009][HNOI2008]GT考试
好劲啊这题……
首先先想DP的做法，我们用[tex]p[i][j][/tex]表示若字符串已匹配前缀[tex][1,i][/tex]，有多少种方案使得追加上一个数后匹配[tex][1,j][/tex]，这个用KMP可以很方便的求出（事实上暴力也可以）。
然后再来看DP的做法，转移方程大致是这样的：
[tex]d[i][j]=\Sigma_{k=0}^{m-1}(d[i-1][k]\times p[k][j])[/tex]
但是n非常大，这么做注定要TLE。
不过看这个转移方程，是不是和矩阵乘法的定义很像？是的。
我们可以用一个[tex]1\times m[/tex]的矩阵[tex]D[/tex]来表示某一个阶段的DP值，我们可以把[tex]p[/tex]组织成一个[tex]m\times m[/tex]矩阵[tex]P[/tex]。然后我们可以发现：
[tex]D_i\times P=D_{i+1}[/tex]
由于矩阵乘法满足结合律，所以：
[tex]D_n=D_0\times P^n[/tex]
很明显可以快速幂搞出来。
代码：
/**************************************************************
Problem: 1009
User: danihao123
Language: C++
Result: Accepted
Time:80 ms
Memory:820 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef ull Matrix[22][22];
ull MOD;
#define REP(i,n) for(i=0;i<(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
#define CP_ARR(from,to) memcpy(to,from,sizeof(from))
inline void MatrixMul(Matrix A,Matrix B,int m,int n,int p,Matrix& res){
register int i,j,k;
Matrix C;
CL_ARR(C,0);
REP(i,m){
REP(j,p){
REP(k,n){
C[i][j]=(C[i][j]+(A[i][k]*B[k][j])%MOD)%MOD;
}
}
}
CP_ARR(C,res);
}
void MatrixPow(Matrix A,int m,ull p,Matrix& res){
Matrix a,temp;
register int i;
CL_ARR(a,0);
memcpy(a,A,sizeof(a));
CL_ARR(temp,0);
REP(i,m){
temp[i][i]=1;
}
while(p){
if(1&p){
MatrixMul(temp,a,m,m,m,temp);
}
p>>=1;
MatrixMul(a,a,m,m,m,a);
}
CP_ARR(temp,res);
}
char buf[25];
int f[25];
int main(){
register int i,u,j;
register ull ret=0;
ull n;
int m;
Matrix ans,P;
scanf("%llu%d%llu",&n,&m,&MOD);
scanf("%s",buf+1);
CL_ARR(ans,0);
ans[0][0]=1;
CL_ARR(P,0);
P[0][0]=9;P[0][1]=1;
// f[0]=f[1]=0;
for(i=1;i<m;i++){
u=f[i];
while(u && buf[u+1]!=buf[i+1]){
u=f[u];
}
if(buf[u+1]==buf[i+1]){
f[i+1]=u+1;
}else{
f[i+1]=0;
}
for(j=0;j<10;j++){
u=i;
while(u && buf[u+1]!=j+'0'){
u=f[u];
}
if(buf[u+1]==j+'0'){
P[i][u+1]=(P[i][u+1]+1)%MOD;
}else{
P[i][0]=(P[i][0]+1)%MOD;
}
}
}
MatrixPow(P,m,n,P);
MatrixMul(ans,P,1,m,m,ans);
for(i=0;i<m;i++){
ret=(ret+ans[0][i])%MOD;
}
printf("%llu\n",ret);
return 0;
}
[BZOJ 2653]middle
前几天想用Github+org-mode替代这个博客，后来想了想，还是算了吧。毕竟博客对大家更方便。
这个题真不愧是陈老师的题啊……exciting！
首先我们看到左端点在[tex][a,b][/tex]，右端点在[tex][c,d][/tex]，一股GSS5的气味扑来？
为了方便，我们先将序列离散化。然后我们将序列中大于等于x的值变为1，小于x的值变为-1，则某段区间的区间和若大于等于0，则该区间的中位数大于等于x，反之则其中位数小于x（注意，此题的中位数定义比较奇怪）。
然后我们可以对每个x建一棵树，然后二分答案，对于每个答案在对应的树上跑一遍GSS5即可（不过这题[tex]a<b<c<d[/tex]，所以不需要复杂的分类讨论）。
但是如果每个x都建一棵树，肯定会MLE吧？这个时候就要用主席树了= =
代码：
/**************************************************************
Problem: 2653
User: danihao123
Language: C++
Result: Accepted
Time:2220 ms
Memory:1956 kb
****************************************************************/
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=20005;
struct Node{
Node *lc,*rc;
int maxPSum,maxSSum,sum;
Node(int x){
lc=rc=NULL;
maxPSum=maxSSum=sum=x;
}
Node(Node *l,Node *r){
lc=l;rc=r;
}
void maintain(){
maxPSum=max(lc->maxPSum,lc->sum+rc->maxPSum);
maxSSum=max(rc->maxSSum,rc->sum+lc->maxSSum);
sum=lc->sum+rc->sum;
}
};
Node* build_tree(int L,int R){
if(L==R){
return new Node(1);
}
int M=L+(R-L)/2;
Node *ans=new Node(build_tree(L,M),build_tree(M+1,R));
ans->maintain();
return ans;
}
int p,v;
Node* insert(Node *o,int L,int R){
if(L==R){
return new Node(v);
}else{
Node *ans=new Node(o->lc,o->rc);
int M=L+(R-L)/2;
if(p<=M){
ans->lc=insert(ans->lc,L,M);
}else{
ans->rc=insert(ans->rc,M+1,R);
}
ans->maintain();
return ans;
}
}
int ql,qr;
Node queryPSum(Node *o,int L,int R){
if(ql<=L && R<=qr){
return *o;
}else{
int M=L+(R-L)/2;
if(qr<=M){
return queryPSum(o->lc,L,M);
}else{
if(ql<=M){
Node l=queryPSum(o->lc,L,M);
Node r=queryPSum(o->rc,M+1,R);
Node ans(l.sum+r.sum);
ans.maxPSum=max(l.maxPSum,l.sum+r.maxPSum);
return ans;
}else{
return queryPSum(o->rc,M+1,R);
}
}
}
}
Node querySSum(Node *o,int L,int R){
if(ql<=L && R<=qr){
return *o;
}else{
int M=L+(R-L)/2;
if(qr<=M){
return querySSum(o->lc,L,M);
}else{
if(ql<=M){
Node l=querySSum(o->lc,L,M);
Node r=querySSum(o->rc,M+1,R);
Node ans(l.sum+r.sum);
ans.maxSSum=max(r.maxSSum,r.sum+l.maxSSum);
return ans;
}else{
return querySSum(o->rc,M+1,R);
}
}
}
}
int querySum(Node *o,int L,int R){
if(ql<=L && R<=qr){
return o->sum;
}else{
int M=L+(R-L)/2;
int ans=0;
if(ql<=M){
ans+=querySum(o->lc,L,M);
}
if(qr>M){
ans+=querySum(o->rc,M+1,R);
}
return ans;
}
}
Node *root[maxn];
int n;
int A[maxn],A2[maxn];
vector<int> V[maxn];
int lsh_siz;
inline void lsh(){
sort(A2+1,A2+1+n);
lsh_siz=unique(A2+1,A2+1+n)-A2-1;
for(register int i=1;i<=n;i++){
A[i]=lower_bound(A2+1,A2+1+lsh_siz,A[i])-A2;
V[A[i]].push_back(i);
}
}
int q[4];
inline bool Check(int M){
register int l,m,r;
if(q[1]+1<=q[2]-1){
ql=q[1]+1;
qr=q[2]-1;
m=querySum(root[M],1,lsh_siz);
}else{
m=0;
}
ql=q[0];qr=q[1];
l=querySSum(root[M],1,lsh_siz).maxSSum;
ql=q[2];qr=q[3];
r=queryPSum(root[M],1,lsh_siz).maxPSum;
#ifdef DEBUG
printf("Case %d: %d %d %d\n",M,l,m,r);
#endif
return l+m+r>=0;
}
int main(){
register int i,j,L,M,R,ans=0;
int t;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&A[i]);
A2[i]=A[i];
}
lsh();
root[1]=build_tree(1,n);
for(i=2;i<=lsh_siz;i++){
root[i]=root[i-1];
for(j=0;j<V[i-1].size();j++){
p=V[i-1][j];
v=-1;
root[i]=insert(root[i],1,lsh_siz);
}
}
scanf("%d",&t);
while(t--){
for(i=0;i<4;i++){
scanf("%d",&q[i]);
q[i]=(q[i]+ans)%n;
}
sort(q,q+4);
for(i=0;i<4;i++){
q[i]++;
#ifdef DEBUG
printf("%d ",q[i]);
if(i==3){
puts("");
}
#endif
}
L=1;R=lsh_siz;
while(true){
if(R-L<=3){
for(i=R;i>=L;i--){
if(Check(i)){
ans=A2[i];
break;
}
}
break;
}
M=L+(R-L)/2;
if(Check(M)){
L=M;
}else{
R=M;
}
}
printf("%d\n",ans);
}
return 0;
}
[BZOJ 2038]小Z的袜子
今年第一更……噫
终于学会莫队了，不过目前只能做这样的模板题……
代码：
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <utility>
using namespace std;
const int maxn=50005;
typedef long long ll;
ll gcd(ll a,ll b){
if(!b){
return a;
}else{
return gcd(b,a%b);
}
}
ll C2(ll n){
register ll temp,ns1=n-1;
if(n&1){
temp=ns1>>1;
return temp*n;
}else{
temp=n>>1;
return temp*ns1;
}
}
struct Node{
int L_s;
int L,R;
int id;
ll ans1,ans2;
};
bool cmp1(const Node& a,const Node& b){
if(a.L_s==b.L_s){
return a.R<b.R;
}else{
return a.L_s<b.L_s;
}
}
bool cmp2(const Node& a,const Node& b){
return a.id<b.id;
}
Node Q[maxn];
int C[maxn],d[maxn];
int n,m;
inline void add_p(int x,ll &ans){
d[x]++;
ans+=d[x]-1;
}
inline void sub_p(int x,ll &ans){
d[x]--;
ans-=d[x];
}
inline void Mo(){
register int i,j,L_p,R_p,sqrt_n=sqrt(n+0.5);
register ll ans,t_gcd,t2;
for(i=1;i<=m;i++){
Q[i].L_s=Q[i].L/sqrt_n;
}
sort(Q+1,Q+1+m,cmp1);
L_p=R_p=Q[1].L;
ans=0;
d[C[L_p]]++;
for(i=1;i<=m;i++){
while(L_p<Q[i].L){
sub_p(C[L_p],ans);
L_p++;
}
while(L_p>Q[i].L){
L_p--;
add_p(C[L_p],ans);
}
while(R_p<Q[i].R){
R_p++;
add_p(C[R_p],ans);
}
while(R_p>Q[i].R){
sub_p(C[R_p],ans);
R_p--;
}
t2=C2(R_p-L_p+1);
t_gcd=gcd(ans,t2);
Q[i].ans1=ans/t_gcd;
Q[i].ans2=t2/t_gcd;
}
sort(Q+1,Q+1+m,cmp2);
}
int main(){
register int i;
int a,b;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d",&C[i]);
}
for(i=1;i<=m;i++){
Q[i].id=i;
scanf("%d%d",&a,&b);
Q[i].L=a;
Q[i].R=b;
}
Mo();
for(i=1;i<=m;i++){
printf("%lld/%lld\n",Q[i].ans1,Q[i].ans2);
}
return 0;
}
[BZOJ 1798]维护序列
万年不更的zzs出现了……
这个题以前竟然没做……近几天做了一下，首交竟然unAC……看样子是我真不会线段树了。
这题不难，唯一需要注意的是乘法标记对加法标记也有影响，而且下传要乘法优先。
代码（警告：此代码exciting）：
/**************************************************************
Problem: 1798
User: danihao123
Language: C++
Result: Accepted
Time:7696 ms
Memory:10980 kb
****************************************************************/
#include <cstdio>
typedef long long ll;
const int maxn=100005;
ll ha;
struct Node{
ll sumv;
int L,R;
ll addv,mulv;
Node *lc,*rc;
Node(ll v,int pos){
sumv=v%ha;
addv=0;
mulv=1;
L=R=pos;
lc=rc=NULL;
}
Node(Node *l,Node *r,int Le,int Ri){
sumv=0;
addv=0;
mulv=1;
L=Le;
R=Ri;
lc=l;
rc=r;
}
void paint_add(ll v){
v=v%ha;
addv=(addv+v)%ha;
ll add_v=(v*((R-L+1)%ha))%ha;
sumv=(sumv+add_v)%ha;
}
void paint_mul(ll v){
v=v%ha;
addv=(addv*v)%ha;
mulv=(mulv*v)%ha;
sumv=(sumv*v)%ha;
}
void maintain(){
if(lc!=NULL && rc!=NULL){
sumv=(lc->sumv+rc->sumv)%ha;
}
}
void pushdown(){
if(mulv!=1){
if(lc!=NULL){
lc->paint_mul(mulv);
}
if(rc!=NULL){
rc->paint_mul(mulv);
}
mulv=1;
}
if(addv!=0){
if(lc!=NULL){
lc->paint_add(addv);
}
if(rc!=NULL){
rc->paint_add(addv);
}
addv=0;
}
}
};
ll A[maxn];
void build_tree(Node* &o,int L,int R){
if(L==R){
o=new Node(A[L],L);
}else{
int M=L+(R-L)/2;
Node *lc,*rc;
build_tree(lc,L,M);
build_tree(rc,M+1,R);
o=new Node(lc,rc,L,R);
o->maintain();
}
}
Node *root;
int ql,qr;
ll v;
ll query_sum(Node *o){
int L=o->L,R=o->R;
o->pushdown();
if(ql<=L && R<=qr){
return o->sumv;
}else{
int M=L+(R-L)/2;
ll ans=0;
if(ql<=M){
ans=(ans+query_sum(o->lc))%ha;
}
if(qr>M){
ans=(ans+query_sum(o->rc))%ha;
}
return ans;
}
}
void update_add(Node *o){
int L=o->L,R=o->R;
o->pushdown();
if(ql<=L && R<=qr){
o->paint_add(v);
}else{
int M=L+(R-L)/2;
if(ql<=M){
update_add(o->lc);
}
if(qr>M){
update_add(o->rc);
}
o->maintain();
}
}
void update_mul(Node *o){
int L=o->L,R=o->R;
o->pushdown();
if(ql<=L && R<=qr){
o->paint_mul(v);
}else{
int M=L+(R-L)/2;
if(ql<=M){
update_mul(o->lc);
}
if(qr>M){
update_mul(o->rc);
}
o->maintain();
}
}
int main(){
register int i;
int n,m,op;
scanf("%d%lld",&n,&ha);
// ha=0x7fffffff;
for(i=1;i<=n;i++){
scanf("%lld",&A[i]);
}
build_tree(root,1,n);
scanf("%d",&m);
while(m--){
scanf("%d%d%d",&op,&ql,&qr);
if(ha==1){
if(op==3){
puts("0");
}else{
scanf("%lld",&v);
}
continue;
}
if(op==1){
scanf("%lld",&v);
update_mul(root);
}else{
if(op==2){
scanf("%lld",&v);
update_add(root);
}else{
printf("%lld\n",query_sum(root));
}
}
}
return 0;
}
[BZOJ 3155]Preprefix sum
蛮有意思的一题……
考虑询问[tex]SS_i[/tex]，[tex][1,i][/tex]中的每个位置[tex]j[/tex]在答案中被计算的次数为[tex]i-j+1[/tex]，然后式子就可以变成这样：
[tex]\Sigma_{j=1}^{i} A[j]*(i-j+1)[/tex]
[tex](i+1)*\Sigma_{j=1}^{i} A[j]-\Sigma_{j=1}^{i} A[j]*j[/tex]
这样问题就简单多了，开两个树状数组乱搞搞即可。
代码：
/**************************************************************
Problem: 3155
User: danihao123
Language: C++
Result: Accepted
Time:464 ms
Memory:3164 kb
****************************************************************/
#include <cstdio>
#include <cstdlib>
const int maxn=100005;
typedef long long ll;
int n;
ll A[maxn];
ll C_1[maxn]; // 正常的BIT
inline int lowbit(int x){
return x&(-x);
}
inline void add(int p,ll v){
while(p<=n){
C_1[p]+=v;
p+=lowbit(p);
}
}
inline ll sum(int p){
register ll ans=0;
while(p>0){
ans+=C_1[p];
p-=lowbit(p);
}
return ans;
}
ll C_2[maxn]; // 累积的BIT
inline void add_2(int p,ll v){
register int pos=p;
while(pos<=n){
C_2[pos]+=((ll)p)*v;
pos+=lowbit(pos);
}
}
inline ll sum_2(int p){
register ll ans=0;
while(p>0){
ans+=C_2[p];
p-=lowbit(p);
}
return ans;
}
int main(){
int m,p;
ll v;
register int i;
char *buf=(char*)calloc(10,1);
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%lld",&A[i]);
add(i,A[i]);
add_2(i,A[i]);
}
while(m--){
scanf("%s%d",buf,&p);
if(buf[0]=='Q'){
printf("%lld\n",((ll)p+1LL)*sum(p)-sum_2(p));
}else{
scanf("%lld",&v);
add(p,v-A[p]);
add_2(p,v-A[p]);
A[p]=v;
}
}
free(buf);
return 0;
}
[BZOJ 3333]排队计划
传说中的大结论题TAT
假设每个数的后面小于它的数的个数为[tex]f[i][/tex]（其位置为[tex]i[/tex]），那么逆序对数显然为[tex]\Sigma f[i][/tex]。
每次操作，只需要将涉及到的数的[tex]f[i][/tex]清为0即可。
为什么呢？任何数的后面比他小的数肯定也被一起拉出来排序了，所以这些数的[tex]f[i][/tex]要被清零。其他数为什么不收这个影响呢？因为这之后的比他小的位置，有的可能没被操作，有的可能被操作了。但是就算被操作了，放到后面位置的数照样会比这个数小（因为这个数如果在第一个选定位置的后面（在前面更是不受影响）还没被操作，肯定比那个第一个位置数还大）。
还有一个细节，一个被操作过的数不需要再被操作一遍，操作完了直接设为INF即可。
代码：
/**************************************************************
Problem: 3333
User: danihao123
Language: C++
Result: Accepted
Time:7920 ms
Memory:24264 kb
****************************************************************/
#include <cstdio>
#include <cctype>
#include <utility>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn=500005;
const int maxnode=maxn*4;
const int INF=0x7fffffff;
int A[maxn];
pii minv[maxnode];
inline void maintain(int o){
minv[o]=min(minv[o<<1],minv[o<<1|1]);
}
void build_tree(int o,int L,int R){
if(L==R){
minv[o]=make_pair(A[L],L);
}else{
int M=L+(R-L)/2;
build_tree(o<<1,L,M);
build_tree(o<<1|1,M+1,R);
maintain(o);
}
}
int ql,qr;
pii query_min(int o,int L,int R){
if(ql<=L && R<=qr){
return minv[o];
}else{
int M=L+(R-L)/2;
pii ans=make_pair(INF,INF);
if(ql<=M)
ans=min(ans,query_min(o<<1,L,M));
if(qr>M)
ans=min(ans,query_min(o<<1|1,M+1,R));
return ans;
}
}
int p;
void update(int o,int L,int R){
if(L==R){
minv[o].first=INF;
}else{
int M=L+(R-L)/2;
if(p<=M)
update(o<<1,L,M);
else
update(o<<1|1,M+1,R);
maintain(o);
}
}
int lsh_siz;
int C[maxn];
inline int lowbit(int x){
return x&(-x);
}
inline void add(int p){
while(p<=lsh_siz){
C[p]++;
p+=lowbit(p);
}
}
inline int sum(int p){
int ans=0;
while(p>0){
ans+=C[p];
p-=lowbit(p);
}
return ans;
}
inline int readint(){
register int x;
register char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return x;
}
int bf[21];
template<typename T>
inline void putint(T x){
register int i,p=0;
if(!x){
bf[p++]=0;
}else{
while(x){
bf[p++]=x%10;
x/=10;
}
}
for(i=p-1;i>=0;i--)
putchar(bf[i]+'0');
putchar('\n');
}
int n;
int A2[maxn],f[maxn];
int main(){
register int i,m,pos;
register ull ans=0;
pii temp;
n=readint();
m=readint();
for(i=1;i<=n;i++){
A[i]=readint();
A2[i]=A[i];
}
sort(A2+1,A2+1+n);
lsh_siz=unique(A2+1,A2+1+n)-A2-1;
for(i=n;i>=1;i--){
pos=lower_bound(A2+1,A2+1+lsh_siz,A[i])-A2;
f[i]=sum(pos-1);
ans+=f[i];
add(pos);
}
putint(ans);
build_tree(1,1,n);
while(m--){
pos=readint();
ql=pos;
qr=n;
while(true){
temp=query_min(1,1,n);
if(temp.first>A[pos])
break;
p=temp.second;
ans-=f[p];
f[p]=0;
update(1,1,n);
}
putint(ans);
}
return 0;
}
[BZOJ 3306]树
这个题其他操作都不难（DFS序+线段树水过），就是换根有点头疼……直接做的话要TopTree吧。
不过我们考虑用DFS序+线段树的“偷懒”做法。每次查询的时候考虑当前的根，如果这个根最初不在x的子树中，那么对目前的查询值没有影响；如果就是x，那么整个树都是x的子树；如果是x的某个后代，那么整个树里除了他的后代所在额这颗子树以外的所有部分全部变成了x的子树（试着翻转一下就明白了）。判断后代祖先以及在哪个子树这些东西可以用倍增LCA高效实现，问题就这样简单了。
代码：
/**************************************************************
Problem: 3306
User: danihao123
Language: C++
Result: Accepted
Time:2308 ms
Memory:17544 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100005;
const int maxnode=maxn*4;
const int INF=0x7fffffff;
#define SEG_STD int o,int L,int R
#define MAKE_MID int M=L+(R-L)/2
// #define MAKE_CLD int lc=o<<1,rc=o<<1|1
#define LCH o<<1,L,M
#define RCH o<<1|1,M+1,R
int n;
int minv[maxnode];
int A[maxn];
void maintain(int o){
minv[o]=min(minv[o<<1],minv[o<<1|1]);
}
void build_tree(SEG_STD){
if(L==R){
minv[o]=A[L];
}else{
MAKE_MID;
build_tree(LCH);
build_tree(RCH);
maintain(o);
}
}
int ql,qr;
int query(SEG_STD){
if(ql<=L && R<=qr){
return minv[o];
}else{
MAKE_MID;
int ans=INF;
if(ql<=M)
ans=min(ans,query(LCH));
if(qr>M)
ans=min(ans,query(RCH));
return ans;
}
}
int p,v;
void update(SEG_STD){
if(L==R){
minv[o]=v;
}else{
MAKE_MID;
if(p<=M)
update(LCH);
else
update(RCH);
maintain(o);
}
}
inline int query(int l,int r){
if(l<1 || l>n || r<1 || r>n)
return INF;
ql=l;
qr=r;
return query(1,1,n);
}
inline void update(int pos,int value){
p=pos;
v=value;
update(1,1,n);
}
int first[maxn];
int next[maxn],to[maxn];
int graph_cnt=0;
inline void AddEdge(int u,int v){
graph_cnt++;
next[graph_cnt]=first[u];
first[u]=graph_cnt;
to[graph_cnt]=v;
}
int d[maxn];
int tid[maxn];
int anc[maxn][19],dep[maxn];
int siz[maxn];
int dfs_clk=0;
void dfs(int x,int fa,int depth){
dfs_clk++;
tid[x]=dfs_clk;
A[dfs_clk]=d[x];
anc[x][0]=fa;
dep[x]=depth;
siz[x]=1;
int i;
for(i=first[x];i;i=next[i]){
dfs(to[i],x,depth+1);
siz[x]+=siz[to[i]];
}
}
void process(){
register int i,j;
for(j=1;(1<<j)<n;j++)
for(i=1;i<=n;i++)
if(anc[i][j-1]!=-1)
anc[i][j]=anc[anc[i][j-1]][j-1];
}
int root;
bool isAnc(int x){
register int p=root,j;
if(dep[p]<dep[x])
return false;
for(j=18;j>=0;j--)
if(dep[p]-(1<<j)>=dep[x] && anc[p][j]!=-1)
p=anc[p][j];
return p==x;
}
int findAnc(int x,int y){
register int j;
for(j=18;j>=0;j--)
if(dep[y]-dep[x]-(1<<j)>0 && anc[y][j]!=-1)
y=anc[y][j];
return y;
}
int getAns(int x){
if(x==root){
return query(1,n);
}else{
if(isAnc(x)){
register int t=findAnc(x,root);
register int l=tid[t],r=tid[t]+siz[t]-1;
return min(query(1,l-1),query(r+1,n));
}else{
return query(tid[x],tid[x]+siz[x]-1);
}
}
}
int main(){
int q,x,f;
register int i;
char buf[3];
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++){
scanf("%d%d",&f,&d[i]);
if(!f){
root=i;
}else{
AddEdge(f,i);
}
}
memset(anc,-1,sizeof(anc));
dfs(root,-1,0);
process();
build_tree(1,1,n);
while(q--){
scanf("%s%d",buf,&x);
if(buf[0]=='V'){
scanf("%d",&f);
update(tid[x],f);
}else{
if(buf[0]=='Q'){
printf("%d\n",getAns(x));
}else{
root=x;
}
}
}
return 0;
}
[BZOJ 2186]沙拉公主的困惑
这个题啊……亦可赛艇！
答案是[tex]\varphi(m!)*n!/m![/tex]。原因很简单，把[tex][1,n!][/tex]分成长度为[tex]m![/tex]的若干段，除去第一段外每一段中与[tex]m![/tex]互质的数[tex]k[/tex]肯定满足[tex](k\bmod m!,m!)=1[/tex]（否则，[tex]k[/tex]和[tex]m![/tex]就会有大于一的公因子了)。所以说每一段内与[tex]m![/tex]互质的数都有[tex]\varphi(m!)[/tex]个。
麻烦好像就在于求一个阶乘的欧拉函数。考虑一个新乘上的数能给答案带来的贡献——如果这个数是合数，它的所有因子在前面都有了，只能把他自己贡献出来；如果这个数是质数（假设为[tex]p[/tex]），出了贡献自己以外还会贡献一个[tex](1-1/p)[/tex]，最后乘起来就是贡献了[tex]p-1[/tex]。筛一遍素数再递推一下就好辣~
并且……[tex]n-m[/tex]可能非常大，所以说除去[tex]m![/tex]那块要用逆元做。
（顺便说下阶乘也要递推）
代码：
/**************************************************************
Problem: 2186
User: danihao123
Language: C++
Result: Accepted
Time:9408 ms
Memory:166836 kb
****************************************************************/
#include <cstdio>
#include <cmath>
typedef unsigned long long ull;
const int maxn=10000000;
ull R;
bool vis[maxn+5];
inline void sievePrime(){
register int i,j,m=sqrt(maxn+0.5);
for(i=2;i<=m;i++)
if(!vis[i])
for(j=i*i;j<=maxn;j+=i)
vis[j]=true;
}
ull fac[maxn+5];
inline void sieveFac(){
register int i;
fac[0]=1%R;
for(i=1;i<=maxn;i++)
fac[i]=(fac[i-1]*(i%R))%R;
}
ull phifac[maxn+5];
inline void sievePhiFac(){
register int i;
phifac[1]=1%R;
for(i=2;i<=maxn;i++){
if(vis[i])
phifac[i]=(phifac[i-1]*(i%R))%R;
else
phifac[i]=(phifac[i-1]*((i%R-1%R+R)%R))%R;
}
}
void exgcd(ull a,ull b,ull& d,ull& x,ull& y){
if(!b){
d=a;
x=1;
y=0;
}else{
exgcd(b,a%b,d,y,x);
y-=x*(a/b);
}
}
ull inv(ull a){
ull d,x,y;
exgcd(a,R,d,x,y);
return (x+R)%R;
}
int main(){
int T;
int n,m;
scanf("%d%llu",&T,&R);
sievePrime();
sieveFac();
sievePhiFac();
while(T--){
scanf("%d%d",&n,&m);
printf("%llu\n",(phifac[m]*((fac[n]*inv(fac[m]))%R))%R);
}
return 0;
}
