天天看点
返回

可持久化线段树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;
}
ACM/ICPC 线段树
上一篇: Section 8-6 : Fourier Series
下一篇: 将一个正整数N用二进制表示并转换为一个String类型的值s

继续阅读