受到主席树深深的暴击。

感觉虽然打回去了然而还是惨败= =

披着高大上名字的虐惨人的可持久化线段树TAT

BZOJ:

BZOJ-4299: Codechef FRBSUM

有这么一个性质：如果当前集合的子集和可以拼凑出[0,i]的所有数,那么也可以拼凑出[1,不大于i+1的所有数的和] 。

这样我们可以类似于倍增的来查询：先从1开始，查询所有比1小的数的和，然后不断+1，直到条件不满足就是答案。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <cstring>
using namespace std;

const int NN = 100010, MM = 6000010;
int n,m,a[NN],cnt=0,mx=0,rt[NN];
struct TR
{
	int sum,lc,rc;
}tr[MM];
void Ins(int x,int &y,int l,int r,int v)
{
	y = ++ cnt;
	tr[y].sum = tr[x].sum + v;
	if (l == r) return;
	tr[y].lc = tr[x].lc, tr[y].rc = tr[x].rc;
	int mid = (l+r) >> 1;
	if (v <= mid) Ins(tr[x].lc,tr[y].lc,l,mid,v); else Ins(tr[x].rc,tr[y].rc,mid+1,r,v);
}
int Query(int x,int y,int l,int r,int v)
{
	if (l > v || !(tr[y].sum-tr[x].sum)) return 0;
	if (v >= r) return tr[y].sum - tr[x].sum;
	int mid = (l+r) >> 1, pre = 0;
	(pre = Query(tr[x].lc,tr[y].lc,l,mid,v)) += (v>mid ? Query(tr[x].rc,tr[y].rc,mid+1,r,v):0);
	return pre;
}
int Ask(int l,int r)
{
	for (int i=1,la;;i=la+1)
	{
		la = Query(rt[l],rt[r],1,mx,i);
		if (la < i) return i;
	}
}
int main()
{
	int l,r;
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]), mx = max(mx,a[i]);
	for (int i=1;i<=n;++i) Ins(rt[i-1],rt[i],1,mx,a[i]);
	scanf("%d",&m);
	for (int _=1;_<=m;++_) scanf("%d%d",&l,&r), printf("%d\n",Ask(l-1,r));
	return 0;
}

BZOJ-3439: Kpm的MC密码

Trie+主席树。

倒着建Trie，用DFS序+主席树查询第k小

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;

#define pb push_back
const int MM = 500010;
int cnt=0,ne[MM][26],num[MM],c[MM],b[MM],d[MM],n;
char ch[MM];
struct TR
{
	int rc,lc,sum;
}tr[MM<<2];
vector <int> Q[MM];
void Ins_ch(int p)
{
	int l = strlen(ch),cc,k=0;
	for (int i=l-1;i>=0;--i,k=ne[k][cc])
		if (!ne[k][cc=ch[i]-'a']) ne[k][cc] = ++cnt;
	num[k]++;
	Q[k].pb(p);
}

void DFS(int xx)
{
	for (int i=0;i<num[xx];++i) c[Q[xx][i]] = cnt+1;
	for (int i=0;i<num[xx];++i) d[++cnt] = Q[xx][i];
	for (int i=0;i<26;++i) if (ne[xx][i]) DFS(ne[xx][i]);
	for (int i=0;i<num[xx];++i) b[Q[xx][i]] = cnt;
} 
void Ins(int xx,int yy,int l,int r,int v)
{
	tr[xx].sum = tr[yy].sum + 1;
	if (l == r) return;
	int mid = (l+r) >> 1;
	if (v <= mid) tr[xx].lc = ++cnt, tr[xx].rc = tr[yy].rc, Ins(tr[xx].lc,tr[yy].lc,l,mid,v);
	else tr[xx].lc = tr[yy].lc, tr[xx].rc = ++cnt, Ins(tr[xx].rc,tr[yy].rc,mid+1,r,v);
}
int Ask(int l,int r,int L,int R,int v)
{
	if (L == R) return L;
	int mid = (L+R) >> 1, tmp = tr[tr[r].lc].sum - tr[tr[l].lc].sum;
	if (tmp >= v) return Ask(tr[l].lc,tr[r].lc,L,mid,v);
	else return Ask(tr[l].rc,tr[r].rc,mid+1,R,v-tmp);
}
int main()
{
	int x;
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%s",ch), Ins_ch(i);
	cnt = 0, DFS(0), cnt = n+1;
	for (int i=1;i<=n;++i) Ins(i+1,i,1,n,d[i]);
	for (int i=1;i<=n;++i)
	{
		scanf("%d",&x);
		if (tr[b[i]+1].sum - tr[c[i]].sum < x) puts("-1");
		else printf("%d\n",Ask(c[i],b[i]+1,1,n,x));
	}
	return 0;
}

BZOJ-3932: [CQOI2015]任务查询系统

以时刻为下标，优先级为区间建主席树。

对于一个区间[l,r]内的任务，l处+1，r+1处-1，然后将时刻i所有发生的时间加入i的树，统计答案。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;

#define pb push_back
typedef long long LL;
const int NN = 100005,INF = 0x3f3f3f3f;

struct TR
{
	int num,lc,rc;
	LL sum;
}tr[NN*80];

vector <int> L[NN],R[NN];
int n,m,rt[NN],cnt,tag,mark[NN*80],mx,mn;
LL ans=1ll;

void Build(int &rt,int xx)
{
	tr[rt = ++cnt] = tr[xx];
	mark[rt] = tag;
}
void Ins(int &rt,int p,int v,int l,int r,int f)
{
	if (mark[p] != tag) Build(rt,p);
	tr[rt].num += f, tr[rt].sum += v*f;
	if (l >= r) return;
	int mid = (l+r) >> 1;
	if (v <= mid) Ins(tr[rt].lc,tr[p].lc,v,l,mid,f);
	else Ins(tr[rt].rc,tr[p].rc,v,mid+1,r,f);
}
LL Query(int x,int l,int r,int k)
{
	if (l >= r) return 1LL*k*l;
	int mid = (l+r) >> 1;
	if (tr[tr[x].lc].num >= k) return Query(tr[x].lc,l,mid,k);
	else return Query(tr[x].rc,mid+1,r,k-tr[tr[x].lc].num) + tr[tr[x].lc].sum;
}
int main()
{
	int x,y,z,w;
	mn = NN, mx = -1;
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i)
	{
		scanf("%d%d%d",&x,&y,&z);
		L[x].pb(z), R[y].pb(z);
		mn = min(mn,x), mx = max(mx,y);
	}
	for (int i=mn;i<=mx;++i)
	{
		Build(rt[i],rt[i-1]); ++tag;
		for (int j=0;j<(int)L[i].size();++j) Ins(rt[i],rt[i],L[i][j],1,INF,1);
		for (int j=0;j<(int)R[i-1].size();++j) Ins(rt[i],rt[i],R[i-1][j],1,INF,-1);
	}
	for (int i=1;i<=m;++i)
	{
		scanf("%d%d%d%d",&w,&x,&y,&z);
		z = 1+(ans*x+y)%z;
		if (z >= tr[rt[w]].num) ans = tr[rt[w]].sum;
		else ans = Query(rt[w],1,INF,z);
		printf("%lld\n",ans);
	}
	return 0;
}

BZOJ-3207: 花神的嘲讽计划Ⅰ

好像是以前做的题了QAQ

把每K个数字hash存起来，然后扔进主席树里，再把询问的hash值在权值线段树中查询

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

#define LL long long
#define NN 200005
#define MM 8000005
#define INF 18446744073709551615UL

int n,m,K,cnt = 0,val[NN],b[NN],rt[NN],sum[MM],a[MM][2];
unsigned LL H[NN],mod = 1UL;

void Ins(int xx,int &yy,unsigned LL val)
{
	yy = ++cnt;
	int tmp = yy;
	sum[yy] = sum[xx] + 1;
	unsigned LL l = 0, r = INF, mid;
	while (l!=r)
	{
		mid = l/2 + r/2;
		if ((l&1) && (r&1)) ++ mid;
		int t = 0;
		if (val > mid) t = 1,l = mid+1; else r = mid-1;
		a[yy][t] = ++cnt;
		a[yy][t^1] = a[xx][t^1];
		xx = a[xx][t] ,yy = a[yy][t], sum[yy] = sum[xx] +1;
	}
	yy = tmp;
}
bool Query(int xx,int yy,unsigned LL val)
{
	unsigned LL l = 0,r = INF,mid;
	while (l!=r)
	{
		mid = l/2 + r/2;
		if ((l&1) && (r&1)) ++mid;
		int t = 0;
		if (val > mid) t = 1, l = mid+1; else r = mid-1;
		xx = a[xx][t] ,yy = a[yy][t];
	}
	return (sum[yy] - sum[xx]) != 0;
}
int main()
{
	n = read(), m = read(), K = read();
	for (int i=1;i<=n;++i) val[i] = read();
	for (int i=1;i<=n;++i) H[i] = H[i-1] * 107+ val[i];
	for (int i=1;i<=K;++i) mod *= 107;
	for (int i=K;i<=n;++i) Ins(rt[i-1],rt[i],H[i]-H[i-K]*mod);
	int x,y;
	while (m--)
	{
		x = read(), y = read();
		for (int i=1;i<=K;++i) b[i] = read();
		unsigned LL now = 0;
		for (int i=1;i<=K;++i) now = now *107 + b[i];
		if (Query(rt[x+K-2],rt[y],now)) puts("No"); else puts("Yes");
	}
	return 0;
}

BZOJ-3218/UOJ#77: a + b Problem

感受到了来自题目名的深深的恶意

第一次见到它在UOJ上QAQ

主席树优化网络流

考虑网络流建边直接建到区间上：

在线段树上，我们应该父亲向儿子连一条容量+∞的边，然后叶子节点在连回相应的i，那么，当1<=j<i，我们将线段树可持久化，然后第i个点向第i-1个版本的线段树连边即可。

然而我们还应将每个叶子节点向它前面的一个版本的叶子节点连边QAQ

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f, NN = 5005, MM = 500005;
int n,z=0,a[NN],l[NN],r[NN],sz,tot=1,cnt=0,rt[NN],ans=0,S,T,g[NN];
int h[MM],head[MM];
queue <int> que;
struct E
{
	int u,v,ne,w;
}e[MM];
struct TR
{
	int lc,rc;
}tr[MM];
void Build(int xx,int yy,int zz)
{
	e[++tot].ne = head[xx], head[xx] = tot, e[tot].u = xx, e[tot].v = yy, e[tot].w = zz;
	e[++tot].ne = head[yy], head[yy] = tot, e[tot].u = yy, e[tot].v = xx, e[tot].w = 0;
}
void Ins(int rt,int l,int r,int L,int R,int v)
{
	if (!rt) return;
	if (l<=L && r>=R) { Build(v,rt,INF); return; }
	int mid = (L+R) >> 1;
	if (l <= mid) Ins(tr[rt].lc,l,r,L,mid,v);
	if (r > mid) Ins(tr[rt].rc,l,r,mid+1,R,v);
}
void Update(int rt,int l,int r,int now,int v,int k)
{
	if (rt) Build(now,rt,INF);
	Build(now,k,INF);
	if (l == r) return;
	int mid = (l+r) >> 1;
	if (v <= mid) tr[now].lc = ++cnt, tr[now].rc = tr[rt].rc, Update(tr[rt].lc,l,mid,cnt,v,k);
	else tr[now].lc = tr[rt].lc, tr[now].rc = ++cnt, Update(tr[rt].rc,mid+1,r,cnt,v,k);
}
bool BFS()
{
	while (!que.empty()) que.pop();
	memset(h,-1,sizeof(h));
	que.push(S), h[S]=0;
	while (!que.empty())
	{
		int now=que.front(); que.pop();
		for (int i=head[now];i;i=e[i].ne)
			if (e[i].w && h[e[i].v]==-1)
				h[e[i].v]=h[now]+1, que.push(e[i].v);
	}
	return h[T]!=-1;
}
int DFS(int xx,int ff)
{
	if (xx==T) return ff;
	int vis=0;
	for (int i=head[xx];i;i=e[i].ne)
	if (e[i].w && h[e[i].v]==h[xx]+1)
	{
		int tmp=DFS(e[i].v,min(e[i].w,ff-vis));
		e[i].w-=tmp; e[i^1].w+=tmp; vis+=tmp;
		if (vis==ff) return ff;
	}
	if (!vis) h[xx]=-1;
	return vis;
}
int Dinic() { int tmp = 0; while (BFS()) tmp+=DFS(S,INF); return tmp;}
int main()
{
	scanf("%d",&n);
	S = 0, T = 2*n+1;
	ans = 0;
	int b,w,p;
	for (int i=1;i<=n;++i)
	{
		scanf("%d%d%d%d%d%d",&a[i],&b,&w,&l[i],&r[i],&p);
		g[i] = a[i];
		ans = ans + b + w;
		Build(S,i,b), Build(i,T,w), Build(i,i+n,p);
	}
	sort(g+1,g+1+n);
	sz = unique(g+1,g+1+n) - g - 1;
	cnt = T;
	for (int i=1;i<=n;++i)
	{
		z = 0;
		int ll = lower_bound(g+1,g+1+sz,l[i])-g, rr = upper_bound(g+1,g+1+sz,r[i])-g-1;
		int now = lower_bound(g+1,g+1+sz,a[i])-g;
		Ins(rt[i-1],ll,rr,1,sz,i+n);
		rt[i] = ++cnt;
		Update(rt[i-1],1,sz,cnt,now,i);
	}
	printf("%d\n",ans-Dinic());
	return 0;
}

BZOJ-4367: [IOI2014]holiday假期

可以分别预处理出: ①只向左走；②只向右走；③向左走并返回；④向右走并返回；这四种情况下能参观的最大景点数

只考虑其中的一种：

用$a[i]$表示只向右走$i$天能参观到的最大景点数

那么我们就要参观景点最多的$i-x+st$个城市，直接用主席树求解会自爆啊啊啊啊啊

又发现对于旅行天数的增加，取最优值得决策点不会向左移动

然后分治求就炒鸡棒咯。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int NN = 250010, MM = 1800010;
int n,m,st,cnt=0,sz,b[NN],sta[NN],rt[NN],fd[NN],gd[NN],f1d[NN],g1d[NN];
LL f[NN],g[NN],f1[NN],g1[NN],pre,ans;
struct TR
{
	LL sum;
	int lc,rc,sz;
}tr[MM];
void Ins(int p,int &rt,int l,int r,int v,LL V)
{
	rt = ++ cnt;
	tr[rt].sz = tr[p].sz + 1, tr[rt].sum = tr[p].sum + V;
	tr[rt].lc = tr[p].lc, tr[rt].rc = tr[p].rc;
	if (l == r) return;
	int mid = (l+r) >> 1;
	if (v <= mid) Ins(tr[p].lc,tr[rt].lc,l,mid,v,V); else Ins(tr[p].rc,tr[rt].rc,mid+1,r,v,V);
}
void Query(int p,int rt,int l,int r,int k)
{
	if (k <= 0) return;
	if (l == r) { pre += 1ll*min(tr[rt].sz-tr[p].sz,k)*sta[l]; return; }
	int mid = (l+r) >> 1;
	if (tr[tr[rt].rc].sz-tr[tr[p].rc].sz >= k) Query(tr[p].rc,tr[rt].rc,mid+1,r,k);
		else pre+=tr[tr[rt].rc].sum-tr[tr[p].rc].sum, Query(tr[p].lc,tr[rt].lc,l,mid,k-tr[tr[rt].rc].sz+tr[tr[p].rc].sz);
}

void Work1(int l,int r,int L,int R)
{
	if (l > r) return;
	int mid = (l+r) >> 1;
	for (int i=L;i<=R;++i)
	{
		pre = 0;
		Query(rt[st-1],rt[i],1,sz,st-i+mid);
		if (pre > f[mid] || !fd[mid]) f[mid] = pre, fd[mid] = i;
	}
	Work1(l,mid-1,L,fd[mid]), Work1(mid+1,r,fd[mid],R);
}
void Work2(int l,int r,int L,int R)
{
	if (l > r) return;
	int mid = (l+r) >> 1;
	for (int i=R;i>=L;--i)
	{
		pre = 0;
		Query(rt[i-1],rt[st-1],1,sz,i-st+mid);
		if (pre > g[mid] || !gd[mid]) g[mid] = pre, gd[mid] = i;
	}
	Work2(l,mid-1,gd[mid],R), Work2(mid+1,r,L,gd[mid]);
}
void Work3(int l,int r,int L,int R)
{
	if (l > r) return;
	int mid = (l+r) >> 1;
	for (int i=L;i<=R;++i)
	{
		pre = 0;
		Query(rt[st-1],rt[i],1,sz,((st-i)<<1)+mid);
		if (pre > f1[mid] || !f1d[mid]) f1[mid] = pre, f1d[mid] = i;
	}
	Work3(l,mid-1,L,f1d[mid]), Work3(mid+1,r,f1d[mid],R);
}
void Work4(int l,int r,int L,int R)
{
	if (l > r) return;
	int mid = (l+r) >> 1;
	for (int i=R;i>=L;--i)
	{
		pre = 0;
		Query(rt[i-1],rt[st-1],1,sz,((i-st)<<1)+mid);
		if (pre > g1[mid] || !g1d[mid]) g1[mid] = pre, g1d[mid] = i;
	}
	Work4(l,mid-1,g1d[mid],R), Work4(mid+1,r,L,g1d[mid]);
}
int main()
{
	scanf("%d%d%d",&n,&st,&m); st ++;
	for (int i=1;i<=n;++i) scanf("%d",&b[i]), sta[i] = b[i];
	sort(sta+1,sta+1+n);
	sz = unique(sta+1,sta+n+1)-sta-1;
	for (int i=1;i<=n;++i)
		b[i] = lower_bound(sta+1,sta+sz+1,b[i])-sta, Ins(rt[i-1],rt[i],1,sz,b[i],sta[b[i]]);
	Work1(1,m,st,min(n,st+m));
	Work2(1,m,max(1,st-m),n);
	Work3(1,m,st,min(n,st+(m>>1)));
	Work4(1,m,max(1,st-(m>>1)),n);
	for (int i=0;i<=m;++i) ans = max(ans,g1[i]+f[m-i]);
	for (int i=0;i<=m;++i) ans = max(ans,f1[i]+g[m-i]);
	printf("%lld\n",ans);
	return 0;
}

BZOJ-3413: 匹配

和字符串有关的题目总是让人心累（难过）

用后缀自动机建棵后缀树，然后用DFS序+主席树

对于每个询问串，找到最后走到的点并求出完成匹配的后缀位置

一直往上走统计答案为该点子树中小于等于完成匹配的后缀位置的后缀的个数*边长度

最后要加上那个完成匹配的后缀位置

Orz Claris

#include <bits/stdc++.h>
using namespace std;
const int NN = 200200;
char ch[NN],s[NN];
bool viss[NN];
int n,m,ans,lens,id,cnt=0,tot=0,fl,fx,ed[NN],st[NN],head[NN],rt[NN],v[NN],w;
struct TR
{
	int lc,rc,sz;
}tr[NN*20];
struct E
{
	int v,w,ne;
}e[NN];
struct SAM
{
	int tot,la,a[NN][30],mx[NN],fa[NN],val[NN];
	SAM(){ la=++tot;}
	void extend(int xx,int ii)
	{
		int p=la,np=la=++tot;
		mx[np]=mx[p]+1,val[np]=ii;
		while (!a[p][xx] && p) a[p][xx]=np,p=fa[p];
		if (!p) fa[np]=1;
		else
		{
			int q=a[p][xx];
			if (mx[p]+1==mx[q]) fa[np]=q;
			else
			{
				int nq=++tot; mx[nq]=mx[p]+1;
				memcpy(a[nq],a[q],sizeof(a[q]));
				fa[nq]=fa[q],fa[np]=fa[q]=nq;
				while (a[p][xx]==q) a[p][xx]=nq,p=fa[p];
			}
		}
	}
}Sam;
void Build(int xx,int yy,int zz)
{
	e[++tot].ne = head[xx], head[xx] = tot, e[tot].v = yy, e[tot].w = zz;
}
void DFS(int xx)
{
	st[xx] = ++id, v[id] = (Sam.val[xx])?n-Sam.mx[xx]:-1;
	for (int i=head[xx];i;i=e[i].ne) DFS(e[i].v);
	ed[xx] = id;
}
void Ins(int p,int &rt,int l,int r,int v)
{
	tr[rt=++cnt].sz = tr[p].sz + 1;
	tr[rt].lc = tr[p].lc, tr[rt].rc = tr[p].rc;
	if (l == r) return;
	int mid = (l+r) >> 1;
	if (v <= mid) Ins(tr[p].lc,tr[rt].lc,l,mid,v); else Ins(tr[p].rc,tr[rt].rc,mid+1,r,v);
}
bool Find()
{
	int w=1,flag=1,i,j;
	fx = 1;
	for (fl=0;w<=lens&&flag;)
		for (flag=0,i=head[fx];i;i=e[i].ne)
			if (ch[e[i].w] == s[w])
			{
				for (fl=j=0;j<min(Sam.mx[e[i].v]-Sam.mx[fx],lens-w+1);++fl,++j)
					if (ch[e[i].w+j] != s[w+j]) { fx = e[i].v; return 0; }
				w += Sam.mx[e[i].v] - Sam.mx[fx];
				fx = e[i].v; flag = 1; break;
			}
	return flag;
			
}
int Get_pos(int x,int y)
{
	int l=0, r=n, mid;
	while (l < r)
	{
		mid = (l+r) >> 1;
		if (tr[tr[y].lc].sz - tr[tr[x].lc].sz) x = tr[x].lc, y = tr[y].lc, r = mid;
		else x = tr[x].rc, y = tr[y].rc, l = mid+1;
	}
	return l;
}
int Ask(int k,int l,int r,int x)
{
	if (!k) return 0;
	if (x >= r) return tr[k].sz;
	int mid = (l+r) >> 1, tmp = Ask(tr[k].lc,l,mid,x);
	if (x > mid) tmp += Ask(tr[k].rc, mid+1,r,x);
	return tmp;
}
int main()
{
	scanf("%d%s",&n,ch+1);
	for (int i=n;i;--i) Sam.extend(ch[i]-'0',i);
	viss[1] = 1;
	for (int i=1;i<=Sam.tot;++i)
		if (Sam.val[i])
			for (int p=n,j=i;!viss[j];j=Sam.fa[j])
				p -= Sam.mx[j] - Sam.mx[Sam.fa[j]], viss[j] = 1, Build(Sam.fa[j],j,p+1);
	DFS(1);
	for (int i=1;i<=id;++i)
		if (v[i] >= 0) Ins(rt[i-1],rt[i],0,n,v[i]);
			else rt[i] = rt[i-1];
	scanf("%d",&m);
	for (;m--;printf("%d\n",ans))
	{
		scanf("%s",s+1);
		lens = strlen(s+1);
		ans = w = Find()?Get_pos(rt[st[fx]-1],rt[ed[fx]]):n;
		ans += fl*(Ask(rt[ed[fx]],0,n,w) - Ask(rt[st[fx]-1],0,n,w));
		for (int x=Sam.fa[fx];x;x=Sam.fa[x])
			ans += (Sam.mx[x]-Sam.mx[Sam.fa[x]]) * (Ask(rt[ed[x]],0,n,w) - Ask(rt[st[x]-1],0,n,w));
	}
	return 0;
}