• 周日. 6月 26th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

7.13

admin

11月 28, 2021

可持久化线段树模板

#include<cstdio>
#include<vector>
#include<algorithm>
#define N 100007
using namespace std;
struct arr{
    int ls,rs,cnt;
}tr[N*20];
vector<int> s;
int n,m,a[N],tot,root[N];
int find(int x){
    return lower_bound(s.begin(),s.end(),x)-s.begin();
}
int build(int l,int r){
    int p=++tot,mid=(l+r)/2;
    if (l==r) return p;
    tr[p].ls=build(l,mid);
    tr[p].rs=build(mid+1,r);
    return p;
}
int inse(int p,int l,int r,int x){
    int q=++tot,mid=(l+r)/2;
    tr[q].ls=tr[p].ls,tr[q].rs=tr[p].rs;
    if (l==r){
        tr[q].cnt++;
        return q;
    }
    if (x<=mid) tr[q].ls=inse(tr[p].ls,l,mid,x);
    else tr[q].rs=inse(tr[p].rs,mid+1,r,x);
    tr[q].cnt=tr[tr[q].ls].cnt+tr[tr[q].rs].cnt;
    return q;
}
int que(int p,int q,int l,int r,int k){
    int mid=(l+r)/2,c;
    if (l==r) return l;
    c=tr[tr[q].ls].cnt-tr[tr[p].ls].cnt;
    if (c>=k) return que(tr[p].ls,tr[q].ls,l,mid,k);
    return que(tr[p].rs,tr[q].rs,mid+1,r,k-c);
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        s.push_back(a[i]);
    }
    sort(s.begin(),s.end());
    s.erase(unique(s.begin(),s.end()),s.end());
    root[0]=build(0,s.size()-1);
    for (int i=1;i<=n;i++)
        root[i]=inse(root[i-1],0,s.size()-1,find(a[i]));
    for (int i=1;i<=m;i++){
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        printf("%d
",s[que(root[l-1],root[r],0,s.size()-1,k)]);
    }
}

treap模板

#include<cstdio>
#include<algorithm>
#define N 1000007
#define INF 1e8
using namespace std;
struct arr{
    int ls,rs,key,val,cnt,size;
}tr[N];
int tot,root,n;
int getnode(int key){
    tr[++tot].key=key;
    srand(tot);
    tr[tot].val=rand();
    tr[tot].cnt=tr[tot].size=1;
    return tot;
}
void renew(int p){
    tr[p].size=tr[tr[p].ls].size+tr[tr[p].rs].size+tr[p].cnt;
}
void zuo(int &p){
    int q=tr[p].rs;
    tr[p].rs=tr[q].ls;
    tr[q].ls=p;
    p=q;
    renew(tr[p].ls),renew(p);
}
void you(int &p){
    int q=tr[p].ls;
    tr[p].ls=tr[q].rs;
    tr[q].rs=p;
    p=q;
    renew(tr[p].rs),renew(p);
}
void build(){
    getnode(-INF),getnode(INF);
    root=1,tr[1].rs=2;
    if (tr[1].val<tr[2].val) zuo(root);
}
void add(int &p,int key){
    if (!p){
        p=getnode(key);
        return;
    }
    if (tr[p].key==key)
        tr[p].cnt++;
    if (tr[p].key<key){
        add(tr[p].rs,key);
        if (tr[tr[p].rs].val>tr[p].val)
            zuo(p);
    }
    if (tr[p].key>key){
        add(tr[p].ls,key);
        if (tr[tr[p].ls].val>tr[p].val)
            you(p);
    }
    renew(p);
}
void del(int &p,int key){
    if (!p) return;
    if (tr[p].key==key)
        if (tr[p].cnt>1) tr[p].cnt--;
        else
        if (tr[p].ls||tr[p].rs)
            if (!tr[p].rs||tr[tr[p].ls].val>tr[tr[p].rs].val){
                you(p);
                del(tr[p].rs,key);
            }
            else{
                zuo(p);
                del(tr[p].ls,key);
            }    
        else p=0;
    else 
    if (tr[p].key>key)
        del(tr[p].ls,key);
    else del(tr[p].rs,key);
    renew(p);
}
int find1(int p,int key){
    if (!p) return 0;
    if (tr[p].key==key) return tr[tr[p].ls].size+1;
    if (tr[p].key>key)
        return find1(tr[p].ls,key);
    return tr[tr[p].ls].size+tr[p].cnt+find1(tr[p].rs,key);
}
int find2(int p,int rank){
    if (!p) return INF;
    if (tr[tr[p].ls].size>=rank) return find2(tr[p].ls,rank);
    if (tr[tr[p].ls].size+tr[p].cnt>=rank) return tr[p].key;
    return find2(tr[p].rs,rank-tr[tr[p].ls].size-tr[p].cnt);
}
int pre(int p,int x){
    if (!p) return -INF;
    if (tr[p].key>=x) return pre(tr[p].ls,x);
    return max(tr[p].key,pre(tr[p].rs,x));
}
int last(int p,int x){
    if (!p) return INF;
    if (tr[p].key<=x) return last(tr[p].rs,x);
    return min(tr[p].key,last(tr[p].ls,x));
}
int main(){
    scanf("%d",&n);
    build();
    for (int i=1;i<=n;i++){
        int opt,x;
        scanf("%d%d",&opt,&x);
        if (opt==1) add(root,x);
        if (opt==2) del(root,x);
        if (opt==3) printf("%d
",find1(root,x)-1);
        if (opt==4) printf("%d
",find2(root,x+1));
        if (opt==5) printf("%d
",pre(root,x));
        if (opt==6) printf("%d
",last(root,x));
    }
}

ac自动机模板

#include<cstdio>
#include<queue>
#include<cstring>
#define N 10001
#define M 1000001
#define S 51
using namespace std;
int ans,tot,n,t,cnt[N*S],tr[N*S][26],ne[N*S];
char s[M];
void add(){
    int p=0;
    for (int i=0;s[i]!='';i++){
        int c=s[i]-'a';
        if (tr[p][c]==0) tr[p][c]=++tot;
        p=tr[p][c];
    }
    cnt[p]++;
}
void build(){
    queue<int>q;
    for (int i=0;i<26;i++)
        if (tr[0][i]!=0)
            q.push(tr[0][i]);
    while (!q.empty()){
        int x=q.front();
        q.pop();
        for (int i=0;i<26;i++)
            if (tr[x][i]!=0){
                int t=tr[x][i],j=ne[x];
                while (j!=0&&tr[j][i]==0) j=ne[j];
                if (tr[j][i]!=0) j=tr[j][i];
                ne[t]=j;
                q.push(t);
            } 
    }
}
int main(){
    scanf("%d",&t);
    while (t--){
        memset(tr,0,sizeof(tr));
        memset(cnt,0,sizeof(cnt));
        memset(ne,0,sizeof(ne));
        tot=0;
        scanf("%d",&n);
        for (int i=1;i<=n;i++){
            scanf("%s",&s);
            add();
        }
        build();
        scanf("%s",&s);
        ans=0;
        for (int i=0,j=0;s[i]!='';i++){
            int c=s[i]-'a';
            while (j!=0&&tr[j][c]==0) j=ne[j];
            if (tr[j][c]!=0) j=tr[j][c];
            for (int p=j;p!=0;p=ne[p])
                ans+=cnt[p],cnt[p]=0;
        }
        printf("%d
",ans);
    }
}

splay模板

#include<cstdio>
#include<algorithm>
#define N 100007
using namespace std;
struct arr{
    int s[2],size,key,p,flag;
}tr[N];
int root,n,m,tot;
void renew(int p){
    tr[p].size=tr[tr[p].s[0]].size+tr[tr[p].s[1]].size+1;
}
void putdown(int x){
    if (tr[x].flag!=0){
        swap(tr[x].s[0],tr[x].s[1]);
        tr[tr[x].s[0]].flag^=1;
        tr[tr[x].s[1]].flag^=1;
        tr[x].flag=0;
    }
}
void rotate(int x){
    int y=tr[x].p,z=tr[y].p;
    int k=tr[y].s[1]==x;
    tr[z].s[tr[z].s[1]==y]=x,tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p = y;
    tr[x].s[k^1]=y,tr[y].p = x;
    renew(y),renew(x);
}
void splay(int x,int k){
    while(tr[x].p!=k){
        int y=tr[x].p,z=tr[y].p;
        if (z!=k)
            if ((tr[y].s[1]==x)^(tr[z].s[1]==y)) rotate(x);
            else rotate(y);
        rotate(x);
    }
    if (!k) root=x;
}
void add(int key){
    int p=0,c,x=root;
    for (;x!=0;p=x,x=tr[x].s[c])
        if (tr[x].key<key) c=1;
        else c=0;
    x=++tot;
    if (p!=0) tr[p].s[c]=x;
    tr[x].p=p,tr[x].key=key;
    splay(x,0);
}
void output(int x){
    putdown(x);
    if (tr[x].s[0]!=0) output(tr[x].s[0]);
    if (tr[x].key>=1&&tr[x].key<=n) printf("%d ",tr[x].key);
    if (tr[x].s[1]!=0) output(tr[x].s[1]);
} 
int get(int x){
    int p=root;
    while (1==1){
        putdown(p);
        if (tr[tr[p].s[0]].size+1>x) p=tr[p].s[0];
        else if (tr[tr[p].s[0]].size+1==x) return p;
        else x-=tr[tr[p].s[0]].size+1,p=tr[p].s[1];
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=0;i<=n+1;i++)
        add(i);
    for (int i=1;i<=m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        l=get(l),r=get(r+2);
        splay(l,0);
        splay(r,l);
        tr[tr[r].s[0]].flag^=1;
    }
    output(root);
}

发表评论

您的电子邮箱地址不会被公开。