可持久化线段树HDU2665、bzoj3207

2024-08-21 21:58
文章标签 持久 线段 bzoj3207 hdu2665

本文主要是介绍可持久化线段树HDU2665、bzoj3207，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=2665

HDU2665..求区间K小。。可以用化分树、各种树来做。也可以用持久化线段树写。

代码：

#include <algorithm>
#include <algorithm>
#include <iostream>
#include<string.h>
#include <fstream>
#include <math.h>
#include <vector>
#include <cstdio>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define exp 1e-8
#define fi first
#define se second
#define ll long long
#define INF 0x3f3f3f3f
#define lson l,mid,rt<<1
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define rson mid+1,r,(rt<<1)+1
#define all(a) a.begin(),a.end()
#define mm(a,b) memset(a,b,sizeof(a));
#define for1(a,b) for(int a=1;a<=b;a++)//1---(b)
#define rep(a,b,c) for(int a=b;a<=c;a++)//b---c
#define repp(a,b,c)for(int a=b;a>=c;a--)///
using namespace std;
void bug(string m="here"){cout<<m<<endl;}
template<typename __ll> inline void READ(__ll &m){__ll 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();}m=x*f;}
template<typename __ll>inline void read(__ll &m){READ(m);}
template<typename __ll>inline void read(__ll &m,__ll &a){READ(m);READ(a);}
template<typename __ll>inline void read(__ll &m,__ll &a,__ll &b){READ(m);READ(a);READ(b);}
template<typename __ll>inline void read(__ll &m,__ll &a,__ll &b,__ll &c){READ(m);READ(a);READ(b);READ(c);}
template < class T > T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template < class T > T lcm(T a, T b) { return a / gcd(a, b) * b; }
template < class T > inline void rmin(T &a, const T &b) { if(a > b) a = b; }
template < class T > inline void rmax(T &a, const T &b) { if(a < b) a = b; }
template < class T > T pow(T a, T b) { T r = 1; while(b > 0) { if(b & 1) r = r * a; a = a * a; b /= 2; } return r; }
template < class T > T pow(T a, T b, T mod) { T r = 1; while(b > 0) { if(b & 1) r = r * a % mod; a = a * a % mod; b /= 2; } return r; }const int maxn=100000;
int sum[maxn*200],tot;
int tree[maxn*200],ls[maxn*200],rs[maxn*200];
void init()
{tot=0;
}
void build(int l,int r,int &rt)
{rt=tot++;sum[rt]=0;if(l==r)return ;int m=l+r>>1;build(l,m,ls[rt]);build(m+1,r,rs[rt]);
}
void update(int last,int p,int l,int r,int &rt)
{rt=tot++;ls[rt]=ls[last],rs[rt]=rs[last],sum[rt]=sum[last]+1;if(l==r)return ;int m=l+r>>1;if(p<=m) update(ls[last],p,l,m,ls[rt]);if(p>m) update(rs[last],p,m+1,r,rs[rt]);
}
int query(int ss,int tt,int l,int r,int k)
{if(l==r)return l;int cnt=sum[ls[tt]]-sum[ls[ss]];int m=r+l>>1;if(k<=cnt)return query(ls[ss],ls[tt],l,m,k);else return query(rs[ss],rs[tt],m+1,r,k-cnt);
}
int num[maxn+100];
int Hash[maxn+100];
void solve()
{int n,m;read(n,m);for1(i,n){read(num[i]);Hash[i]=num[i];}sort(Hash+1,Hash+1+n);int cnt=unique(Hash+1,Hash+1+n)-Hash-1;for1(i,n)num[i]=lower_bound(Hash+1,Hash+1+cnt,num[i])-Hash;init();build(1,cnt,tree[0]);for1(i,n)update(tree[i-1],num[i],1,cnt,tree[i]);for1(i,m){int a,b,c;read(a,b,c);printf("%d\n",Hash[query(tree[a-1],tree[b],1,cnt,c)]);}
}
int main()
{int cas;read(cas);while(cas--)solve();
}



http://acm.upc.edu.cn/problem.php?id=2224

题意：给一个序列，求区间【li,ri】内大小在【a,b】区间的数的多少。。

#include <algorithm>
#include <algorithm>
#include <iostream>
#include<string.h>
#include <fstream>
#include <math.h>
#include <vector>
#include <cstdio>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define exp 1e-8
#define fi first
#define se second
#define ll long long
#define INF 0x3f3f3f3f
#define lson l,mid,rt<<1
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define rson mid+1,r,(rt<<1)+1
#define all(a) a.begin(),a.end()
#define mm(a,b) memset(a,b,sizeof(a));
#define for1(a,b) for(int a=1;a<=b;a++)//1---(b)
#define rep(a,b,c) for(int a=b;a<=c;a++)//b---c
#define repp(a,b,c)for(int a=b;a>=c;a--)///
using namespace std;
void bug(string m="here"){cout<<m<<endl;}
template<typename __ll> inline void READ(__ll &m){__ll 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();}m=x*f;}
template<typename __ll>inline void read(__ll &m){READ(m);}
template<typename __ll>inline void read(__ll &m,__ll &a){READ(m);READ(a);}
template<typename __ll>inline void read(__ll &m,__ll &a,__ll &b){READ(m);READ(a);READ(b);}
template<typename __ll>inline void read(__ll &m,__ll &a,__ll &b,__ll &c){READ(m);READ(a);READ(b);READ(c);}
template < class T > T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template < class T > T lcm(T a, T b) { return a / gcd(a, b) * b; }
template < class T > inline void rmin(T &a, const T &b) { if(a > b) a = b; }
template < class T > inline void rmax(T &a, const T &b) { if(a < b) a = b; }
template < class T > T pow(T a, T b) { T r = 1; while(b > 0) { if(b & 1) r = r * a; a = a * a; b /= 2; } return r; }
template < class T > T pow(T a, T b, T mod) { T r = 1; while(b > 0) { if(b & 1) r = r * a % mod; a = a * a % mod; b /= 2; } return r; }const int maxn=50000;
int tree[maxn*20],ls[maxn*20],rs[maxn*20];
int sum[maxn*20],tot;
void init(){tot=0;}
void pushup(int rt)
{sum[rt]=sum[ls[rt]]+sum[rs[rt]];
}
void build(int l,int r,int &rt)
{rt=tot++;sum[rt]=0;if(l==r)return ;int m=r+l>>1;build(l,m,ls[rt]);build(m+1,r,rs[rt]);
}
void update(int last,int p,int l,int r,int &rt)
{rt=tot++;ls[rt]=ls[last],rs[rt]=rs[last];sum[rt]=sum[last]+1;if(l==r)return;int m=r+l>>1;if(p<=m)update(ls[last],p,l,m,ls[rt]);else    update(rs[last],p,m+1,r,rs[rt]);
}
int query(int ss,int tt,int l,int r,int L,int R)
{if(L<=l&&r<=R)return sum[tt]-sum[ss];int m=l+r>>1;int ret=0;if(L<=m)ret+=query(ls[ss],ls[tt],l,m,L,R);if(R>m)ret+=query(rs[ss],rs[tt],m+1,r,L,R);return ret;
}
int num[maxn+100];
int Hash[maxn+100];
void solve()
{int n,m;read(n,m);for1(i,n){read(num[i]);Hash[i]=num[i];}sort(Hash+1,Hash+1+n);int cnt=unique(Hash+1,Hash+1+n)-Hash-1;for1(i,n)num[i]=lower_bound(Hash+1,Hash+1+cnt,num[i])-Hash;init();build(1,cnt,tree[0]);for1(i,n)update(tree[i-1],num[i],1,cnt,tree[i]);while(m--){int a,b,c,d;read(a,b);read(c,d);c=lower_bound(Hash+1,Hash+1+cnt,c)-Hash;d=upper_bound(Hash+1,Hash+1+cnt,d)-Hash-1;if(d<c)puts("0");else printf("%d\n",query(tree[a-1],tree[b],1,cnt,c,d));}
}
int main()
{int cas;read(cas);for1(tt,cas){printf("Case #%d:\n",tt);solve();}return 0;
}

bzoj 3207.... http://www.lydsy.com/JudgeOnline/problem.php?id=3207

题意：给一个序列，问某一个区间内是否有规定的子串。子串长度为k...

一开始还真不知道怎么做~~~居然还要hash.....

可以通过hash将子串转成一个数。原来的序列也通过hash转换成n-k+1个数。。。

题目就变为在某个区间内寻找某一个数是否存在。。。OMG...ORZ...

#include <algorithm>
#include <algorithm>
#include <iostream>
#include<string.h>
#include <fstream>
#include <math.h>
#include <vector>
#include <cstdio>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define exp 1e-8
#define fi first
#define se second
#define ll long long
#define INF 0x3f3f3f3f
#define lson l,mid,rt<<1
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define rson mid+1,r,(rt<<1)+1
#define all(a) a.begin(),a.end()
#define mm(a,b) memset(a,b,sizeof(a));
#define for1(a,b) for(int a=1;a<=b;a++)//1---(b)
#define rep(a,b,c) for(int a=b;a<=c;a++)//b---c
#define repp(a,b,c)for(int a=b;a>=c;a--)///
using namespace std;
void bug(string m="here"){cout<<m<<endl;}
template<typename __ll> inline void READ(__ll &m){__ll 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();}m=x*f;}
template<typename __ll>inline void read(__ll &m){READ(m);}
template<typename __ll>inline void read(__ll &m,__ll &a){READ(m);READ(a);}
template<typename __ll>inline void read(__ll &m,__ll &a,__ll &b){READ(m);READ(a);READ(b);}
template<typename __ll>inline void read(__ll &m,__ll &a,__ll &b,__ll &c){READ(m);READ(a);READ(b);READ(c);}
template < class T > T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template < class T > T lcm(T a, T b) { return a / gcd(a, b) * b; }
template < class T > inline void rmin(T &a, const T &b) { if(a > b) a = b; }
template < class T > inline void rmax(T &a, const T &b) { if(a < b) a = b; }
template < class T > T pow(T a, T b) { T r = 1; while(b > 0) { if(b & 1) r = r * a; a = a * a; b /= 2; } return r; }
template < class T > T pow(T a, T b, T mod) { T r = 1; while(b > 0) { if(b & 1) r = r * a % mod; a = a * a % mod; b /= 2; } return r; }const int maxn=100000+10;   //第一次不知道范围开了好大好大。。TLE
int tree[maxn*50],ls[maxn*50],rs[maxn*50];
int sum[maxn*50],tot;
void init(){tot=0;}
void build(int l,int r,int &rt)
{rt=tot++;sum[rt]=0;if(l==r)return ;int m=r+l>>1;build(l,m,ls[rt]);build(m+1,r,rs[rt]);
}
void update(int pre,int p,int l,int r,int &rt)
{rt=tot++;ls[rt]=ls[pre],rs[rt]=rs[pre];sum[rt]=sum[pre]+1;if(l==r)return ;int m=r+l>>1;if(p<=m)update(ls[pre],p,l,m,ls[rt]);else  update(rs[pre],p,m+1,r,rs[rt]);
}
bool query(int ss,int tt,int p,int l,int r)
{if(l==r)return sum[tt]>sum[ss];int m=l+r>>1;if(p<=m)return query(ls[ss],ls[tt],p,l,m);return query(rs[ss],rs[tt],p,m+1,r);
}
unsigned ll num[maxn];
unsigned ll f[maxn];
unsigned ll dat[maxn];
unsigned ll Hash[maxn];
int main()
{int n,m,k;read(n,m,k);for1(i,n)read(num[i]);for1(i,n)f[i]=f[i-1]*107+num[i];unsigned ll M=1;for1(i,k)M*=107;for(int i=k;i<=n;i++){dat[i-k+1]=f[i]-f[i-k]*M;Hash[i-k+1]=dat[i-k+1];}int cnt=n-k+1;sort(Hash+1,Hash+1+cnt);cnt=unique(Hash+1,Hash+1+cnt)-Hash-1;for(int i=1;i<=n-k+1;i++)dat[i]=lower_bound(Hash+1,Hash+1+cnt,dat[i])-Hash;init();build(1,cnt,tree[0]);for1(i,n-k+1)update(tree[i-1],dat[i],1,cnt,tree[i]);while(m--){int a,b,c;read(a,b);unsigned ll ret=0;for1(i,k){read(c);ret=ret*107+c;}if(b-a+1<k){puts("No");continue;}int idx=lower_bound(Hash+1,Hash+1+cnt,ret)-Hash;a--;b=b-k+1;if(!Hash[idx]||Hash[idx]!=ret)puts("Yes");else if(!query(tree[a],tree[b],idx,1,cnt)) puts("Yes");else puts("No");}return 0;
}


这篇关于可持久化线段树HDU2665、bzoj3207的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1094395。

相关文章

Redis事务与数据持久化方式

Redis事务与数据持久化方式

《Redis事务与数据持久化方式》该文档主要介绍了Redis事务和持久化机制,事务通过将多个命令打包执行,而持久化则通过快照（RDB）和追加式文件（AOF）两种方式将内存数据保存到磁盘,以防止数据丢失... 目录一、Redis 事务1.1 事务本质1.2 数据库事务与redis事务1.2.1 数据库事务1.
阅读更多...
poj3468(线段树成段更新模板题)

poj3468(线段树成段更新模板题)

题意：包括两个操作：1、将[a.b]上的数字加上v；2、查询区间[a,b]上的和 下面的介绍是下解题思路： 首先介绍  lazy－tag思想：用一个变量记录每一个线段树节点的变化值，当这部分线段的一致性被破坏我们就将这个变化值传递给子区间，大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作，那么就从根节点[1,n]开始调用update函数进行操作，如果刚好执行到一个子节点，
阅读更多...
hdu1394(线段树点更新的应用)

hdu1394(线段树点更新的应用)

题意：求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质，在0到n-1这些数字组成的乱序排列，将第一个数字A移到最后一位，得到的逆序数为res-a+(n-a-1) 知道上面的知识点后，可以用暴力来解 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in
阅读更多...
hdu1689(线段树成段更新)

hdu1689(线段树成段更新)

两种操作：1、set区间[a,b]上数字为v；2、查询[ 1 , n ]上的sum 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl
阅读更多...
hdu 1754 I Hate It（线段树，单点更新，区间最值）

hdu 1754 I Hate It（线段树，单点更新，区间最值）

题意是求一个线段中的最大数。 线段树的模板题，试用了一下交大的模板。效率有点略低。 代码： #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :
阅读更多...
hdu 1166 敌兵布阵（树状数组 or 线段树）

hdu 1166 敌兵布阵（树状数组 or 线段树）

题意是求一个线段的和，在线段上可以进行加减的修改。 树状数组的模板题。 代码： #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while
阅读更多...
poj 1127 线段相交的判定

poj 1127 线段相交的判定

题意： 有n根木棍，每根的端点坐标分别是 px, py, qx, qy。 判断每对木棍是否相连，当他们之间有公共点时，就认为他们相连。 并且通过相连的木棍相连的木棍也是相连的。 解析： 线段相交的判定。 首先，模板中的线段相交是不判端点的，所以要加一个端点在直线上的判定； 然后，端点在直线上的判定这个函数是不判定两个端点是同一个端点的情况的，所以要加是否端点相等的判断。 最后
阅读更多...
HDU4737线段树

HDU4737线段树

题目大意：给定一系列数，F(i,j)表示对从ai到aj连续求或运算，(i<=j)求F(i,j)<=m的总数。 const int Max_N = 100008 ;int sum[Max_N<<2] , x[Max_N] ;int n , m ;void push_up(int t){sum[t] = sum[t<<1] | sum[t<<1|1] ;}void upd
阅读更多...
zoj 1721 判断2条线段（完全）相交

zoj 1721 判断2条线段（完全）相交

给出起点，终点，与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离，然后最短路。 2点可达条件：没有线段与这2点所构成的线段（完全）相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;
阅读更多...
圆与线段的交点

圆与线段的交点

poj 3819  给出一条线段的两个端点，再给出n个圆，求出这条线段被所有圆覆盖的部分占了整条线段的百分比。 圆与线段的交点 ： 向量AB 的参数方程  P = A + t * (B - A)      0<=t<=1 ； 将点带入圆的方程即可。  注意： 有交点 0 <= t <= 1 ; 此题求覆盖的部分。 则 若求得 t  满足 ; double ask(d
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2