主席树 | OceanEye's Blog

BZOJ3932

裸的主席树

前k个可能是一个优先级的一部分

看代码吧:-D

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <iostream>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')

char cc; int C;
template <class T>
void read( T &x )
{
	x=0; cc=getchar(); C=1;
	while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
	x*=C;
}

using namespace std;
#define N 100010

struct rec
{
	int id,pos,val;
}RRR[N<<1];
int ____;

bool comp(const rec &x,const rec &y)
{ return x.id<y.id; }

int n,m,p;

void pre()
{
	read(n); read(m);
	int _,__,___;
	for(int i=1;i<=n;i++)
	{
		read(_); read(__); read(___);
		RRR[____].id=_; RRR[____].val=1; RRR[____].pos=___; ____++;
		RRR[____].id=__+1; RRR[____].val=-1; RRR[____].pos=___; ____++;
	}
	sort(RRR,RRR+____,comp);
}

struct node
{
	int l,r,c[2],cnt;
	ll sum;
}pool[N<<6];
#define L pool[x].l
#define R pool[x].r
#define Lc pool[x].c[0]
#define Rc pool[x].c[1]
#define SUM pool[x].sum
#define CNT pool[x].cnt

int RT[N],pcnt;

void PushUP(int x)
{
	SUM=pool[Lc].sum+pool[Rc].sum;
	CNT=pool[Lc].cnt+pool[Rc].cnt;
}

void insert(const int &pos,int& x,const int &val)
{
	pool[++pcnt]=pool[x]; x=pcnt;
	if(L==R) { CNT+=val; SUM=1LL*CNT*pos; return; }
	int mid=(L+R)>>1;
	if(mid>=pos)
	{
		if(Lc==0)pool[Lc].l=L,pool[Lc].r=mid;
		insert(pos,Lc,val);
	}
	else
	{
		if(Rc==0)pool[Rc].l=mid+1,pool[Rc].r=R;
		insert(pos,Rc,val);
	}
	PushUP(x);
}

ll sum(int x,int k)
{
	if(x==0) return 0;
	if(CNT<=k) return SUM;
	if(L==R) { return (ll)min(k,CNT)*L; }
	return pool[Lc].cnt>=k?sum(Lc,k):pool[Lc].sum+sum(Rc,k-pool[Lc].cnt);
}

int main()
{
	freopen("BZOJ3932.in","r",stdin);
	pre();
	____=0;
	pool[0].l=1; pool[0].r=10000050;
	for(int i=1;i<=m;i++)
	{
		RT[i]=RT[i-1];
		for(;RRR[____].id==i;____++)
			insert(RRR[____].pos,RT[i],RRR[____].val);
	}
	static int Q,T,A,B,C,k,mid;
	ll pre=1;
	while(m--)
	{
		read(T); read(A); read(B); read(C);
		pre%=C; A%=C; B%=C;
		k=1+(ll)(1LL*A*pre+B)%C;
		printf("%lld\n",pre=sum(RT[T],k));
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <iostream>

#define ll long long

#define INF 1000000000

#define p(x) ('0'<=x&&x<='9')

char cc; int C;

template <class T>

void read( T &x )

{

x=0; cc=getchar(); C=1;

while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=C;

}

using namespace std;

#define N 100010

struct rec

{

int id,pos,val;

}RRR[N<<1];

int ____;

bool comp(const rec &x,const rec &y)

{ return x.id<y.id; }

int n,m,p;

void pre()

{

read(n); read(m);

int _,__,___;

for(int i=1;i<=n;i++)

{

read(_); read(__); read(___);

RRR[____].id=_; RRR[____].val=1; RRR[____].pos=___; ____++;

RRR[____].id=__+1; RRR[____].val=-1; RRR[____].pos=___; ____++;

}

sort(RRR,RRR+____,comp);

}

struct node

{

int l,r,c[2],cnt;

ll sum;

}pool[N<<6];

#define L pool[x].l

#define R pool[x].r

#define Lc pool[x].c[0]

#define Rc pool[x].c[1]

#define SUM pool[x].sum

#define CNT pool[x].cnt

int RT[N],pcnt;

void PushUP(int x)

{

SUM=pool[Lc].sum+pool[Rc].sum;

CNT=pool[Lc].cnt+pool[Rc].cnt;

}

void insert(const int &pos,int& x,const int &val)

{

pool[++pcnt]=pool[x]; x=pcnt;

if(L==R) { CNT+=val; SUM=1LL*CNT*pos; return; }

int mid=(L+R)>>1;

if(mid>=pos)

{

if(Lc==0)pool[Lc].l=L,pool[Lc].r=mid;

insert(pos,Lc,val);

}

else

{

if(Rc==0)pool[Rc].l=mid+1,pool[Rc].r=R;

insert(pos,Rc,val);

}

PushUP(x);

}

ll sum(int x,int k)

{

if(x==0) return 0;

if(CNT<=k) return SUM;

if(L==R) { return (ll)min(k,CNT)*L; }

return pool[Lc].cnt>=k?sum(Lc,k):pool[Lc].sum+sum(Rc,k-pool[Lc].cnt);

}

int main()

{

freopen("BZOJ3932.in","r",stdin);

pre();

____=0;

pool[0].l=1; pool[0].r=10000050;

for(int i=1;i<=m;i++)

{

RT[i]=RT[i-1];

for(;RRR[____].id==i;____++)

insert(RRR[____].pos,RT[i],RRR[____].val);

}

static int Q,T,A,B,C,k,mid;

ll pre=1;

while(m--)

{

read(T); read(A); read(B); read(C);

pre%=C; A%=C; B%=C;

k=1+(ll)(1LL*A*pre+B)%C;

printf("%lld\n",pre=sum(RT[T],k));

}

return 0;

}

BZOJ3932

BZOJ4299 CodeChef FRBSUM

OceanEye 撰写 BZOJ CodeChef 主席树线段树无回复

很强的题目= =超级烦

想来想去想不懂怎么写

一个很朴素的想法就是排序然后一个一个加进去

假设当前已经满足可以取[0,P]之间的取值

新进来一个数q

如果q在[0,P+1]之间的话就可以拓展 P -> P+q

否则停止拓展，因为显然后面那一堆都不满足要求

然后我就不会了= =跑去翻了翻题解 [传送门]

发现可以连着处理一段的sum，时间复杂度大致是单次log方的。

真神奇

#include <cstdio>
#include <algorithm>
#define ll long long
#define p(x)  ('0'<=x&&x<='9')
char cc;
template <class T> 
void read( T &x )
{
	cc=getchar(); x=0;
	while(!p(cc)) cc=getchar();
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
}

using namespace std;
#define N 100010
#define inf 1000000000
namespace Segent_Tree
{
	struct node
	{
		int lc,rc;
		ll sum;
	}pool[N<<6];
#define Lc pool[x].lc
#define Rc pool[x].rc
#define LC pool[x2].lc
#define RC pool[x2].rc
#define SUM pool[x].sum
#define VAL pool[x].val
#define DEC pool[x].sum-pool[x2].sum
	int pcnt,rt[N],now;
	void init()
	{
//		pool[rt[0]].l=1; pool[rt[0]].r=N;
		pcnt=rt[0]=1;
	}
	void PushUP(int x) { SUM=pool[Lc].sum+pool[Rc].sum; }
	void insert(int &x,const ll & val,int l,int r)
	{
		pool[++pcnt]=pool[x]; x=pcnt;
		if(l==r)
		{
			pool[x].sum+=val;
			return;
		}
		int mid=(l+r)>>1;
		if(mid>=val) insert(pool[x].lc,val,l,mid);
		else insert(pool[x].rc,val,mid+1,r);
		PushUP(x);
	}
	void add(ll x)
	{
		rt[now+1]=rt[now]; now++;
		insert(rt[now],x,1,inf);
	}
	ll query(int x2,int x,int l,int r,int L,int R)
	{
		if(L<=l&&r<=R)
		{
			return DEC;
		}
		int mid=(l+r) >>1;
		ll ret=0;
		if(mid>=L) ret+=query(LC,Lc,l,mid,L,R);
		if(mid+1<=R) ret+=query(RC,Rc,mid+1,r,L,R);
		return ret;
	}
	ll solve(int l,int r)
	{
		ll mx=1,p=query(rt[l-1],rt[r],1,inf,1,1);
		while(p>=mx)
		{
			mx=p+1;
			p=query(rt[l-1],rt[r],1,inf,1,mx);
		}
		return mx;
	}
}
int n,_,__;
int main()
{
	Segent_Tree::init();
	read(n);
	while(n--)
	{
		read(_);
		Segent_Tree::add(_);
	}
	read(n);
	while(n--)
	{
		read(_); read(__);
		if(_>__) swap(_,__);
		printf("%lld\n",Segent_Tree::solve(_,__));
	}
	return 0;
}

#include <cstdio>

#include <algorithm>

#define ll long long

#define p(x) ('0'<=x&&x<='9')

char cc;

template <class T>

void read( T &x )

{

cc=getchar(); x=0;

while(!p(cc)) cc=getchar();

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

}

using namespace std;

#define N 100010

#define inf 1000000000

namespace Segent_Tree

{

struct node

{

int lc,rc;

ll sum;

}pool[N<<6];

#define Lc pool[x].lc

#define Rc pool[x].rc

#define LC pool[x2].lc

#define RC pool[x2].rc

#define SUM pool[x].sum

#define VAL pool[x].val

#define DEC pool[x].sum-pool[x2].sum

int pcnt,rt[N],now;

void init()

{

// pool[rt[0]].l=1; pool[rt[0]].r=N;

pcnt=rt[0]=1;

}

void PushUP(int x) { SUM=pool[Lc].sum+pool[Rc].sum; }

void insert(int &x,const ll & val,int l,int r)

{

pool[++pcnt]=pool[x]; x=pcnt;

if(l==r)

{

pool[x].sum+=val;

return;

}

int mid=(l+r)>>1;

if(mid>=val) insert(pool[x].lc,val,l,mid);

else insert(pool[x].rc,val,mid+1,r);

PushUP(x);

}

void add(ll x)

{

rt[now+1]=rt[now]; now++;

insert(rt[now],x,1,inf);

}

ll query(int x2,int x,int l,int r,int L,int R)

{

if(L<=l&&r<=R)

{

return DEC;

}

int mid=(l+r) >>1;

ll ret=0;

if(mid>=L) ret+=query(LC,Lc,l,mid,L,R);

if(mid+1<=R) ret+=query(RC,Rc,mid+1,r,L,R);

return ret;

}

ll solve(int l,int r)

{

ll mx=1,p=query(rt[l-1],rt[r],1,inf,1,1);

while(p>=mx)

{

mx=p+1;

p=query(rt[l-1],rt[r],1,inf,1,mx);

}

return mx;

}

int n,_,__;

int main()

{

Segent_Tree::init();

read(n);

while(n--)

{

read(_);

Segent_Tree::add(_);

}

read(n);

while(n--)

{

read(_); read(__);

if(_>__) swap(_,__);

printf("%lld\n",Segent_Tree::solve(_,__));

}

return 0;

}

BZOJ4299 CodeChef FRBSUM

51nod 1681 主席树

OceanEye 撰写主席树线段树无回复

这题主席树的处理还是有点神的，，
maya我直接~~抄题解~~就好了，，反正我方法的和题解是一样的。
但是我比好多人都慢啊QAQ不服气

首先转化问题。两棵树的公共祖先，很扯淡。计算出每两个点的两棵树上的公共祖先我用的复杂度是n^2·logn
妈呀根本不能接受，妥妥的TLE
那么我们计算祖先的贡献怎么样？
首先假设某个点有x个公共儿子，那么他对总的亲密度的贡献是x*(x-1)/2【自己脑补组合数】
但是看一眼数据范围，首先O(n)应该是不可能的了。那么我们能不能在nlogn的时间内瞎搞出所有节点的公共儿子呢qwq
平衡树？搞毛，，线段树？搞毛，，树剖？不好意思不会，，主席树？于是又神奇的想到了转化问题

他的标号是混乱的，这很不清真，，换成DFS序怎么样？
第二棵树呢？还是混乱的，，

混乱又怎么样，，再标一次就好了。这个时候我们要的就是完成两个集合求交集的工作。
那么主席树出场了！

第一棵树的节点先按照dfs序重新编号，记节点A的子节点为l到r
然后第二棵树也这么做，，记节点A的子节点为L到R
这个时候，会惊奇发现他们的公共儿子【交集】不就是求[L,R]中有多少个元素属于[l,r]的么，，
由于这个东西目测满足区间加法，所以主席树应该是可行的。
那么就主席树瞎搞一下，，A掉。
爽！

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int maxn = 100050;
const int NIL = 0;

struct Tr
{
	int lc,rc,cnt,l,r;
}pool[maxn*20];

struct node
{
	int num,l,r,L,R;
}a[maxn];

vector <int> T[maxn];
int n,i,j,x,y,T_cnt,id[maxn],root[maxn];
bool vis[maxn];

void dfs2(int k,int &cnt)
{
	id[cnt] = k; int cur = cnt;
	for(int i=0;i<T[k].size();i++)
		dfs2(T[k][i],++cnt);
	if (T[k].size() > 0) { a[k].L = cur+1; a[k].R = cnt; }
	T[k].clear();
}

void dfs1(int k,int &cnt)
{
	a[k].num = cnt;
	for(int i=0;i<T[k].size();i++)
		dfs1(T[k][i],++cnt);
	if (T[k].size() > 0) { a[k].l = a[k].num+1; a[k].r = cnt; }
	T[k].clear();
}

void insert(int &x,int num,int l,int r)
{
	pool[T_cnt++] = pool[x]; x = T_cnt-1; pool[x].cnt++;
	pool[x].l = min(pool[x].l,num); pool[x].r = max(pool[x].r,num);
	if (l==r) return;
	int mid = (l+r)>>1;
	if(num <= mid) insert(pool[x].lc,num,l,mid);
	else insert(pool[x].rc,num,mid+1,r);
}

int query(int i,int j,int l,int r)
{
	if (pool[j].l > r || pool[j].r < l) return 0;
	if (pool[j].l >= l && pool[j].r <= r) return pool[j].cnt - pool[i].cnt;
	if (pool[j].l==pool[j].r) return 0;
	return query(pool[i].lc,pool[j].lc,l,r) + query(pool[i].rc,pool[j].rc,l,r);
}

int main()
{
	scanf("%d",&n);
	memset(vis,false,sizeof(vis));
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		vis[y] = true; T[x].push_back(y);
	}
	for(i=1;i<=n;i++)
		if (!vis[i])
		{
			int cnt = 1;
			dfs1(i,cnt);
			break;
		}
	memset(vis,false,sizeof(vis));
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		vis[y] = true; T[x].push_back(y);
	}
	for(i=1;i<=n;i++) if(!vis[i])
	{
		int cnt = 1;
		dfs2(i,cnt);
	}
	T_cnt = 1; pool[0].lc = pool[0].rc = pool[0].cnt = NIL; root[NIL] = NIL; pool[0].l = maxn; pool[0].r = 0; 
	for(i=1;i<=n;i++)
	{
		root[i] = root[i-1];
		insert(root[i],a[id[i]].num,1,n);
	}
	long long ans = 0;
	for(i=1;i<=n;i++)
	{
		int k = query(root[a[id[i]].L-1],root[a[id[i]].R],a[id[i]].l,a[id[i]].r);
		ans += (1ll)*k*(k-1)/2;
	}
	printf("%lld\n",ans);
	return 0;
}

100

101

102

103

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <cstring>

#include <vector>

using namespace std;

const int maxn = 100050;

const int NIL = 0;

struct Tr

{

int lc,rc,cnt,l,r;

}pool[maxn*20];

struct node

{

int num,l,r,L,R;

}a[maxn];

vector <int> T[maxn];

int n,i,j,x,y,T_cnt,id[maxn],root[maxn];

bool vis[maxn];

void dfs2(int k,int &cnt)

{

id[cnt] = k; int cur = cnt;

for(int i=0;i<T[k].size();i++)

dfs2(T[k][i],++cnt);

if (T[k].size() > 0) { a[k].L = cur+1; a[k].R = cnt; }

T[k].clear();

}

void dfs1(int k,int &cnt)

{

a[k].num = cnt;

for(int i=0;i<T[k].size();i++)

dfs1(T[k][i],++cnt);

if (T[k].size() > 0) { a[k].l = a[k].num+1; a[k].r = cnt; }

T[k].clear();

}

void insert(int &x,int num,int l,int r)

{

pool[T_cnt++] = pool[x]; x = T_cnt-1; pool[x].cnt++;

pool[x].l = min(pool[x].l,num); pool[x].r = max(pool[x].r,num);

if (l==r) return;

int mid = (l+r)>>1;

if(num <= mid) insert(pool[x].lc,num,l,mid);

else insert(pool[x].rc,num,mid+1,r);

}

int query(int i,int j,int l,int r)

{

if (pool[j].l > r || pool[j].r < l) return 0;

if (pool[j].l >= l && pool[j].r <= r) return pool[j].cnt - pool[i].cnt;

if (pool[j].l==pool[j].r) return 0;

return query(pool[i].lc,pool[j].lc,l,r) + query(pool[i].rc,pool[j].rc,l,r);

}

int main()

{

scanf("%d",&n);

memset(vis,false,sizeof(vis));

for(i=1;i<n;i++)

{

scanf("%d%d",&x,&y);

vis[y] = true; T[x].push_back(y);

}

for(i=1;i<=n;i++)

if (!vis[i])

{

int cnt = 1;

dfs1(i,cnt);

break;

}

memset(vis,false,sizeof(vis));

for(i=1;i<n;i++)

{

scanf("%d%d",&x,&y);

vis[y] = true; T[x].push_back(y);

}

for(i=1;i<=n;i++) if(!vis[i])

{

int cnt = 1;

dfs2(i,cnt);

}

T_cnt = 1; pool[0].lc = pool[0].rc = pool[0].cnt = NIL; root[NIL] = NIL; pool[0].l = maxn; pool[0].r = 0;

for(i=1;i<=n;i++)

{

root[i] = root[i-1];

insert(root[i],a[id[i]].num,1,n);

}

long long ans = 0;

for(i=1;i<=n;i++)

{

int k = query(root[a[id[i]].L-1],root[a[id[i]].R],a[id[i]].l,a[id[i]].r);

ans += (1ll)*k*(k-1)/2;

}

printf("%lld\n",ans);

return 0;

}

OceanEye's Blog

很多人即使只见过一面，已经算见过了最后一面。

@OceanEye7年前

BZOJ3932

BZOJ3932

@OceanEye7年前

BZOJ4299 CodeChef FRBSUM

BZOJ4299 CodeChef FRBSUM

@OceanEye7年前

51nod 1681 主席树

51nod 1681 主席树

友情链接

近期文章

标签