12
5
2015
0

【bzoj3524】【Poi2014】Couriers

3524: [Poi2014]Couriers

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 899  Solved: 300
[Submit][Status][Discuss]

Description

给一个长度为n的序列a。1≤a[i]≤n。
m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。

 

Input

第一行两个数n，m。
第二行n个数，a[i]。
接下来m行，每行两个数l,r，表示询问[l,r]这个区间。

 

Output

m行，每行对应一个答案。

 

Sample Input

7 5
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6
 

Sample Output

1
0
3
0
4
 

HINT

【数据范围】

n,m≤500000

Source

By Dzy

一道裸的可持久化线段树。询问时，如果左儿子的区间数字出现数大于(r-l+1)/2，那么右儿子的的区间数字出现数不会达到(r-l+1)/2，因此也不存在数出现数大于(r-l+1)/2，所以只要去访问左儿子就可以了，同理，如果右儿子的区间数字出现数大于(r-l+1)/2，就去访问右儿子，如果两者都不满足，就返回0。

解决啦！！

代码：

 

/**************************************************************
    Problem: 3524
    User: yeweining
    Language: C++
    Result: Accepted
    Time:6248 ms
    Memory:121900 kb
****************************************************************/
 
#include<cstdio>
using namespace std;
int n,m,a[500010],root[500010],l,r,cnt,tmp;
struct node{int l,r,sum;}tr[10000010];
void change(int l,int r,int &p,int x)
{
    tr[++cnt]=tr[p];p=cnt;tr[p].sum++;
    if (l==r) return;
    int mid=(l+r)>>1;
    if (x<=mid) change(l,mid,tr[p].l,x);else change(mid+1,r,tr[p].r,x);
}
int ask(int l,int r,int p1,int p2)
{
    if (l==r) return l;
    int mid=(l+r)>>1;
    if (tr[tr[p2].l].sum-tr[tr[p1].l].sum>tmp) return ask(l,mid,tr[p1].l,tr[p2].l);else
    if (tr[tr[p2].r].sum-tr[tr[p1].r].sum>tmp) return ask(mid+1,r,tr[p1].r,tr[p2].r);else return 0;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for (int i=1;i<=n;i++)
    {
        root[i]=root[i-1];
        change(1,n,root[i],a[i]);
    }
    while (m--)
    {
        scanf("%d%d",&l,&r);
        tmp=(r-l+1)>>1;
        printf("%d\n",ask(1,n,root[l-1],root[r]));
    }
}

 

Category: 可持久化线段树 | Tags:
12
4
2015
0

【bzoj3674】可持久化并查集加强版

3674: 可持久化并查集加强版

Time Limit: 15 Sec  Memory Limit: 256 MB
Submit: 1053  Solved: 381
[Submit][Status][Discuss]

Description

Description：
自从zkysb出了可持久化并查集后……
hzwer:乱写能AC，暴力踩标程
KuribohG：我不路径压缩就过了！
ndsf：暴力就可以轻松虐！
zky:……

n个集合 m个操作
操作：
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合，是则输出1否则输出0
请注意本题采用强制在线,所给的a,b,k均经过加密,加密方法为x = x xor lastans,lastans的初始值为0
0<n,m<=2*10^5

 

Input

 

Output

 

Sample Input

5 6
1 1 2
3 1 2
2 1
3 0 3
2 1
3 1 2

Sample Output

1
0
1

HINT

 

Source

出题人大SB++

好吧，我承认我确实打可持久化数据结构有点上瘾了，因为它的魅力着实让我欲罢不能。。。

回归本题。

此题我们只要维护每一次的并查集的fa数组，由于时间问题，我们还需要维护连通块中点的个数来按秩合并。要维护数组，我们可以用可持久化线段树来维护，线段树的叶子节点就是这个数组，这样就可以维护每次的并查集了。

代码：

 

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,opt,x,y,x1,x2,ans,cnt,root[210010];
struct node{int l,r,fa,num;}tr[15000010];
void change(int l,int r,int &p,int x,int fa,int num)
{
	tr[++cnt]=tr[p];p=cnt;
	if (l==r){tr[p].fa=fa;tr[p].num=num;return;}
	int mid=(l+r)>>1;
	if (x<=mid) change(l,mid,tr[p].l,x,fa,num);else change(mid+1,r,tr[p].r,x,fa,num);
}
int ask(int l,int r,int p,int x)
{
	if (l==r) return p;
	int mid=(l+r)>>1;
	if (x<=mid) return ask(l,mid,tr[p].l,x);else return ask(mid+1,r,tr[p].r,x);
}
int getfather(int p,int x)
{
	int t=ask(1,n,p,x);
	if (tr[t].fa==x) return t;else return getfather(p,tr[t].fa);
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		change(1,n,root[0],i,i,1);
	for (int i=1;i<=m;i++)
	{
		scanf("%d",&opt);
		root[i]=root[i-1];
		if (opt==1)
		{
			scanf("%d%d",&x,&y);
			x^=ans;y^=ans;
			x1=getfather(root[i],x);x2=getfather(root[i],y);
			if (tr[x1].fa==tr[x2].fa) continue;
			if (tr[x1].num>tr[x2].num) swap(x1,x2);
			change(1,n,root[i],tr[x1].fa,tr[x2].fa,0);
			change(1,n,root[i],tr[x2].fa,tr[x2].fa,tr[x2].num+tr[x1].num);
		}else
		if (opt==2)
		{
			scanf("%d",&x);
			x^=ans;
			root[i]=root[x];
		}else
		{
			scanf("%d%d",&x,&y);
			x^=ans;y^=ans;
			x1=getfather(root[i],x);x2=getfather(root[i],y);
			if (tr[x1].fa==tr[x2].fa) ans=1;else ans=0;
			printf("%d\n",ans);
		}
	}
}
Category: 可持久化线段树 | Tags:
12
2
2015
0

【bzoj3207】花神的嘲讽计划Ⅰ

3207: 花神的嘲讽计划Ⅰ

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1065  Solved: 389
[Submit][Status][Discuss]

Description

背景
花神是神，一大癖好就是嘲讽大J，举例如下：
“哎你傻不傻的！【hqz：大笨J】”
“这道题又被J屎过了！！”
“J这程序怎么跑这么快！J要逆袭了！”
……
描述
这一天DJ在给吾等众蒟蒻讲题，花神在一边做题无聊，就跑到了一边跟吾等众蒟蒻一起听。以下是部分摘录：
1.
“J你在讲什么！”
“我在讲XXX！”
“哎你傻不傻的！这么麻烦，直接XXX再XXX就好了！”
“……”
2.
“J你XXX讲过了没？”
“……”
“那个都不讲你就讲这个了？哎你傻不傻的！”
“……”
DJ对这种情景表示非常无语，每每出现这种情况，DJ都是非常尴尬的。
经过众蒟蒻研究，DJ在讲课之前会有一个长度为N方案，我们可以把它看作一个数列；
同样，花神在听课之前也会有一个嘲讽方案，有M个，每次会在x到y的这段时间开始嘲讽，为了减少题目难度，每次嘲讽方案的长度是一定的，为K。
花神嘲讽DJ让DJ尴尬需要的条件：
在x~y的时间内DJ没有讲到花神的嘲讽方案，即J的讲课方案中的x~y没有花神的嘲讽方案【这样花神会嘲讽J不会所以不讲】。
经过众蒟蒻努力，在一次讲课之前得到了花神嘲讽的各次方案，DJ得知了这个消息以后欣喜不已，DJ想知道花神的每次嘲讽是否会让DJ尴尬【说不出话来】。
 

Input

第1行3个数N，M，K；
第2行N个数，意义如上；
第3行到第3+M-1行，每行K+2个数，前两个数为x,y,然后K个数，意义如上；

Output

对于每一个嘲讽做出一个回答会尴尬输出‘Yes’，否则输出‘No’

Sample Input

8 5 3
1 2 3 4 5 6 7 8
2 5 2 3 4
1 8 3 2 1
5 7 4 5 6
2 5 1 2 3
1 7 3 4 5

Sample Output

No
Yes
Yes
Yes
No

HINT

 

题中所有数据不超过2*10^9;保证方案序列的每个数字<=N
2~5中有2 3 4的方案，输出No，表示DJ不会尴尬
1~8中没有3 2 1的方案，输出Yes，表示DJ会尴尬
5~7中没有4 5 6的方案，输出Yes，表示DJ会尴尬
2~5中没有1 2 3的方案，输出Yes，表示DJ会尴尬
1~7中有3 4 5的方案，输出No，表示DJ不会尴尬

Source

原创 Memphis

又练了一道可持久化线段树。。。

只要把一开始i这个点的权值变为i~i+k-1这段的hash值。然后就非常容易了。

代码：

 

/**************************************************************
    Problem: 3207
    User: yeweining
    Language: C++
    Result: Accepted
    Time:5644 ms
    Memory:96900 kb
****************************************************************/
 
#include<cstdio>
using namespace std;
typedef unsigned long long ull;
int n,m,k,root[100010],x,y,x1,cnt;
int a[100010];
ull mi[100010],h[100010],x2,INF;
struct node{int l,r,sum;}tr[8000010];
void change(int &p,ull l,ull r,ull x)
{
    tr[++cnt]=tr[p];p=cnt;tr[p].sum++;
    if (l==r) return;
    ull mid=l/2+r/2;
    if ((l&1)&&(r&1)) mid++;
    if (x<=mid) change(tr[p].l,l,mid,x);else change(tr[p].r,mid+1,r,x);
}
bool ask(int p1,int p2,ull l,ull r,ull x)
{
    if (l==r) return (tr[p2].sum>tr[p1].sum);
    ull mid=l/2+r/2;
    if ((l&1)&&(r&1)) mid++;
    if (x<=mid) return ask(tr[p1].l,tr[p2].l,l,mid,x);else return ask(tr[p1].r,tr[p2].r,mid+1,r,x);
}
ull get(int i){return h[i+k-1]-h[i-1]*mi[k];}
int main()
{
    INF=18446744073709551615UL;
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    mi[0]=1;
    for (int i=1;i<=n;i++)
        mi[i]=mi[i-1]*10007;
    for (int i=1;i<=n;i++)
        h[i]=h[i-1]*10007+a[i];
    for (int i=1;i<=n-k+1;i++)
    {
        root[i]=root[i-1];
        change(root[i],0,INF,get(i));
    }
    while (m--)
    {
        scanf("%d%d",&x,&y);
        ull x2=0;
        for (int i=1;i<=k;i++)
        {
            scanf("%d",&x1);
            x2=x2*10007+x1;
        }
        if (ask(root[x-1],root[y-k+1],0,INF,x2)) printf("No\n");else printf("Yes\n");
    }
}
Category: 可持久化线段树 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com