[BZOJ 3295][CQOI2011]动态逆序对

又一道坑了很久没有写题解的……

删除操作特别的棘手,但好在我们可以离线~时光倒流之后,删除就变成了添加。

每个点加进来之后,对答案的贡献可以分为两部分:

  1. 加入比他早,位置在他前面,值比他大的点。
  2. 加入比他早,位置在他后面,值比他小的点。

然后两者都可以用CDQ统计(我还偷懒用同一个CDQ做的)

代码:

/**************************************************************
    Problem: 3295
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2332 ms
    Memory:5768 kb
****************************************************************/
 
#include <cstdio>
#include <stack>
#include <algorithm>
using std::stack;
using std::sort;
const int maxn = 100005;
typedef long long ll;
struct Query {
    int id;
    int p, v;
};
 
int n;
ll C[maxn];
int lowbit(int x) {
    return x & (-x);
}
void add(int p, int v) {
    while(p <= n) {
        C[p] += v;
        p += lowbit(p);
    }
}
ll sum(int p) {
    ll ret = 0;
    while(p > 0) {
        ret += C[p];
        p -= lowbit(p);
    }
    return ret;
}
int query(int l, int r) {
    return sum(r) - sum(l - 1);
}
void clean(int p) {
    while(p <= n && C[p] != 0) {
        C[p] = 0;
        p += lowbit(p);
    }
}
 
Query A[maxn], tmp[maxn];
ll ans[maxn];
void CDQ(int L, int R, bool flag) {
    if(L == R) {
        return;
    }
    int M = L + (R - L) / 2;
    CDQ(L, M, flag); CDQ(M + 1, R, flag);
    for(int p = L, l = L, r = M + 1; p <= R; p ++) {
        if(r > R || (l <= M && (flag ? A[l].p < A[r].p : A[l].p > A[r].p))) {
            tmp[p] = A[l];
            add(A[l].v, 1);
            l ++;
        } else {
            tmp[p] = A[r];
            ans[A[r].id] += query(A[r].v + 1, n);
            r ++;
        }
    }
    for(int i = L; i <= M; i ++) {
        clean(A[i].v);
    }
    for(int i = L; i <= R; i ++) {
        A[i] = tmp[i];
    }
}
bool cmp_id(const Query& a, const Query& b) {
    return a.id < b.id;
}
 
int arr[maxn];
bool del[maxn];
int pos[maxn];
stack<int> delS;
int main() {
    int m;
    scanf("%d%d", &n, &m);
    int id_siz = 0;
    for(int i = 1; i <= n; i ++) {
        scanf("%d", &arr[i]);
    }
    for(int i = 1; i <= m; i ++) {
        int a;
        scanf("%d", &a);
        delS.push(a);
        del[a] = true;
    }
    for(int i = 1; i <= n; i ++) {
        if(del[arr[i]]) {
            pos[arr[i]] = i;
        } else {
            id_siz ++;
            A[id_siz].id = id_siz;
            A[id_siz].p = i;
            A[id_siz].v = arr[i];
        }
    }
    while(!delS.empty()) {
        int a = delS.top(); delS.pop();
        id_siz ++;
        A[id_siz].id = id_siz;
        A[id_siz].p = pos[a];
        A[id_siz].v = a;
    }
    CDQ(1, n, true);
    sort(A + 1, A + 1 + n, cmp_id);
    for(int i = 1; i <= n; i ++) {
        A[i].v = n - A[i].v + 1;
    }
    CDQ(1, n, false);
    for(int i = 1; i <= n; i ++) {
        ans[i] += ans[i - 1];
    }
    for(int i = 0; i < m; i ++) {
        printf("%lld\n", ans[n - i]);
    }
    return 0;
}

[BZOJ 2733][HNOI2012]永无乡

我这题竟然很早就做了……

求k小显然可以用平衡树。但是这个题还需要快速的合并平衡树,那就需要启发式合并了。

继续阅读

[BZOJ 1483][HNOI2009]梦幻布丁

做了很久了吧,但现在才写题解……(斜眼

首先记录一个起始的颜色段数,然后每种颜色都要用链表顺序记下该颜色有哪些点。然后合并的时候合并两个链表——最优策略显然是启发式合并。

但是,很多时候并不是把小链表的扔到大的里面的情况,而是恰好反过来的情况,如何处理?

这种时候,我们可以交换两个颜色的“真实身份”。合并的时候,把每个点当成它的“真实身份”处理即可。

继续阅读

[BZOJ 3252]攻略

近期心情不顺,坑了一堆没写的题解……(嗯我反演等回来再填坑吧(逃

好了还是说说这题吧,私以为鄙人的做法还是蛮妙的:

定义\(d(x)\)表示\(x\)到根上所有点的权值和,\(d_{max}(x)\)为\(x\)所在的子树中所有点的\(d(x)\)的最大值。对一个结点,他的所有儿子中\(d_{max}(x)\)最大的称为重儿子,其他作为轻儿子,然后做一遍树剖。然后将所有重链的权值和扔到一个数组里,降序排序,选前\(k\)大求和即可(不够的话全选)。

为什么?

显然,尽可能选叶子是划算的。然后,任意一条重链链顶的父亲所在的重链的权值和必定大于该重链,所以说不必担心某个重链选了而他的祖先却没有被记到答案里的情况。而若干这种重链的并,恰好对应了若干条到叶子路径的并。由于我们还是从大到小选的,所以答案是最优的。

继续阅读

[坑]狄利克雷卷积和反演

开个坑,记录一些和反演以及狄利克雷卷积的东西。

首先积性函数、狄利克雷卷积等基本概念不写了,就讲讲性质吧。

有几个一定要记住的东西:

\[\mu \ast 1 = e\]

\[\varphi \ast 1 = id\]

\[\mu \ast id = \varphi\]

这几个在推式子的过程中都有很大的作用,务必要记住。

所谓莫比乌斯反演,其实就是:

\[F = f \ast 1\Leftrightarrow f = F \ast \mu\]

(谜之音:其实很多所谓“反演题”都没用到这俩性质啊……)

关于莫比乌斯函数本身,还有一个好康的性质:

\[(\mu\ast 1)(k) = \sum_{i = 0}^k (-1)^i C_k^i\]

继续阅读

[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;
}

[POJ 1149]PIGS

这个题是经典的网络流题目。在经过一次次的思想过滤后你会发现,这个问题的瓶颈(换猪)大可以理解为前面的顾客给后面的留一些不是?这样问题就简单多了。

按顺序整理出到访每个猪圈的顾客,对于到访每个猪圈的第一个顾客,从[tex]S[/tex]向其连一条容量为此猪圈中猪的数量的边。然后每个猪圈前面一个顾客要个给后面的留一些猪,这个可以直接连一条容量为无限大的边来表示。

最后每个顾客向[tex]T[/tex]连一条容量为其买猪数量上限的边,然后求一遍[tex]S[/tex]到[tex]T[/tex]的最大流,问题得解。

这个题还有一个优化就是,有一些边是可以合并的(比如说从[tex]S[/tex]流出的一些边是可能指向同一顾客的,同一对顾客之间的连边数可能不止1条),但是我没有做这个优化,照样A了……

代码:

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using std::vector;
using std::queue;
using std::min;
const int maxn=105,maxm=1005;
namespace Dinic{
	struct Edge{
		int u,v,cap,flow;
	};
	vector<Edge> edges;
	vector<int> G[maxn];
	int s,t;
	int m;
	inline void AddEdge(int u,int v,int cap){
		edges.push_back((Edge){u,v,cap,0});
		edges.push_back((Edge){v,u,0,0});
		m=edges.size();
		G[u].push_back(m-2);
		G[v].push_back(m-1);
	}
	bool vis[maxn];
	int d[maxn];
	inline bool bfs(){
		register int i,u,siz;
		queue<int> Q;
		memset(vis,0,sizeof(vis));
		d[s]=0;
		Q.push(s);
		vis[s]=true;
		while(!Q.empty()){
			u=Q.front();Q.pop();
			siz=G[u].size();
			for(i=0;i<siz;i++){
				Edge& e=edges[G[u][i]];
				if(!vis[e.v] && e.cap>e.flow){
					d[e.v]=d[u]+1;
					Q.push(e.v);
					vis[e.v]=true;
				}
			}
		}
		return vis[t];
	}
	int cur[maxn];
	int dfs(int x,int a){
		if(x==t || a==0){
			return a;
		}
		int f,flow=0,siz=G[x].size();
		for(int& i=cur[x];i<siz;i++){
			Edge& e=edges[G[x][i]];
			if(d[e.v]==d[x]+1){
				f=dfs(e.v,min(a,e.cap-e.flow));
				if(f>0){
					flow+=f;
					e.flow+=f;
					edges[G[x][i]^1].flow-=f;
					a-=f;
					if(a==0){
						break;
					}
				}
			}
		}
		if(a>0){
			d[x]=-1;
		}
		return flow;
	}
	inline int solve(int S,int T){
		register int ans=0;
		s=S;t=T;
		while(bfs()){
			memset(cur,0,sizeof(cur));
			ans+=dfs(s,0x7fffffff);
		}
		return ans;
	}
};
using Dinic::AddEdge;
using Dinic::solve;
int pigs[maxm];
vector<int> Use[maxm];
int main(){
	register int i,j;
	int m,n;
	scanf("%d%d",&m,&n);
	for(i=1;i<=m;i++){
		scanf("%d",&pigs[i]);
	}
	for(i=1;i<=n;i++){
		int a,b,temp;
		scanf("%d",&a);
		for(j=1;j<=a;j++){
			scanf("%d",&temp);
			Use[temp].push_back(i);
		}
		scanf("%d",&b);
		AddEdge(i,n+1,b);
	}
	for(i=1;i<=m;i++){
		AddEdge(0,Use[i][0],pigs[i]);
		int siz=Use[i].size();
		for(j=1;j<siz;j++){
			AddEdge(Use[i][j-1],Use[i][j],0x7f7f7f7f);
		}
	}
	printf("%d\n",solve(0,n+1));
	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 1176][Balkan2007]Mokia

CDQ分治第一题……同时也是CDQ分治模板提。

感觉CDQ分治思路好秒啊……似乎在分治过程中做了个归并排序……

代码:

/**************************************************************
    Problem: 1176
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4364 ms
    Memory:17228 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxw=2000005;
const int maxq=10005;
const int maxn=160001+4*maxq;
int cnt=0;
struct Query{
  int ans_id;
  int x,y,d,v;
  Query(){}
  Query(int a,int b,int di,int ap){
    x=a;y=b;
    d=di;
    ans_id=ap;
  }
  Query(int a,int b,int value){
    x=a;y=b;
    v=value;
    d=0;
  }
  inline bool isQuery(){
    return d!=0;
  }
};
 
int w;
int T[maxw];
inline int lowbit(int x){
  return x&(-x);
}
inline void add(int p,int v){
  while(p<=w){
    T[p]+=v;
    p+=lowbit(p);
  }
}
inline int sum(int p){
  register int x=0;
  while(p>0){
    x+=T[p];
    p-=lowbit(p);
  }
  return x;
}
inline void clear(int p){
  while(p<=w && T[p]!=0){
    T[p]=0;
    p+=lowbit(p);
  }
}
 
Query Q[maxn],tmp[maxn];
int ans[maxn];
void CDQ(int L,int R){
  if(L==R){
    return;
  }
  int M=L+(R-L)/2;
  CDQ(L,M);
  CDQ(M+1,R);
  int p,p1,p2;
  for(p=1,p1=L,p2=M+1;p<=(R-L+1);p++){
    if((Q[p1].x<=Q[p2].x && p1<=M) || p2>R){
      tmp[p]=Q[p1];
      if(!Q[p1].isQuery()){
        add(Q[p1].y,Q[p1].v);
      }
      p1++;
    }else{
      tmp[p]=Q[p2];
      if(Q[p2].isQuery()){
        ans[Q[p2].ans_id]+=sum(Q[p2].y)*Q[p2].d;
      }
      p2++;
    }
  }
  for(p=1,p1=L;p<=(R-L+1);p++,p1++){
    if(!Q[p1].isQuery()){
      clear(Q[p1].y);
    }
    Q[p1]=tmp[p];
  }
}
 
int main(){
  int S,t,x,y,a,b;
  register int ans_cnt=0;
  scanf("%d%d",&S,&w);
  while(true){
    scanf("%d",&t);
    if(t==3){
      break;
    }
    scanf("%d%d%d",&x,&y,&a);
    // x++;y++;
    if(t==1){
      Q[++cnt]=Query(x,y,a);
    }else{
      scanf("%d",&b);
      // a++;b++;
      ans_cnt++;
      ans[ans_cnt]=(a-x+1)*(b-y+1)*S;
      Q[++cnt]=Query(a,b,1,ans_cnt);
      Q[++cnt]=Query(x-1,b,-1,ans_cnt);
      Q[++cnt]=Query(a,y-1,-1,ans_cnt);
      Q[++cnt]=Query(x-1,y-1,1,ans_cnt);
    }
  }
  CDQ(1,cnt);
  for(register int i=1;i<=ans_cnt;i++){
    printf("%d\n",ans[i]);
  }
  return 0;
}