POJ3580 SuperMemo splay伸展树,区间操作

时间：2022-06-22 13:38:07

题意:实现一种数据结构，支持对一个数列的 6 种操作：
第 x 个数到第 y 个数之间的数每个加 D；
第 x 个数到第 y 个数之间全部数翻转；
第 x 个数到第 y 个数之间的数，向后循环流动 c 次，即后面 c个数变成这段子序列的最前面 c 个，前面的被挤到后面。
在第 x 个数后面插入一个数 P。
删除第 x 个数。
求第 x 个数到第 y 个数之间的最小数字。

题解:

(待补)

代码先放上:

(是真的长啊,我已经是比较压行的选手了,依然写了230行)

1.利用stack回收内存池

#include <cstdio>

#include <stack>

#include <cstring>

#include <vector>

#define ll long long

#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)

using namespace std;

const int maxn=1e6+10,maxm=2e6+10;

const int INF=0x3f3f3f3f;

class splaytree{

	public:

	struct splaynode{

		splaynode *son[2],*pre;

		ll val,tag,mn;

		int size,rev;

		void init(ll x){

			pre=son[1]=son[0]=NULL;

			mn=val=x;

			tag=rev=0;

			size=1;

		}

		void add(ll x){tag+=x,mn+=x;}

	};

	typedef struct splaynode* nodep;

  int cnt;

  stack<nodep> stk;

  nodep root;

	vector<splaynode> node;

  int getsize(nodep x){return x?x->size:0;}

  void pushdown(nodep now){

    if(!now) return ;

    if(now->tag){

      ll tag=now->tag;

      now->val+=tag;

      if(now->son[0]) now->son[0]->add(tag);

      if(now->son[1]) now->son[1]->add(tag);

      now->tag=0;

    }

    if(now->rev){

      swap(now->son[0],now->son[1]);

      now->rev=0;

      if(now->son[0]) now->son[0]->rev^=1;

      if(now->son[1]) now->son[1]->rev^=1;

    }

  }

  void pushup(nodep now){

    if(!now) return ;

    now->size=1,now->mn=now->val;

    if(now->son[0]) {

      now->mn=min(now->mn,now->son[0]->mn);

      now->size+=now->son[0]->size;

    }

    if(now->son[1]){

      now->mn=min(now->mn,now->son[1]->mn);

      now->size+=now->son[1]->size;

    }

  }

  void rotate(nodep now,int d){

    nodep fa=now->pre;

    pushdown(fa);

    pushdown(now);

    pushdown(now->son[d]);

    fa->son[!d]=now->son[d];

    if(now->son[d]) now->son[d]->pre=fa;

    now->pre=fa->pre;

    if(fa->pre){

      if(fa->pre->son[0]==fa) fa->pre->son[0]=now;

      else fa->pre->son[1]=now;

    }else root=now;

    now->son[d]=fa;

    fa->pre=now;

    pushup(fa);

  }

  void splay(nodep now,nodep dst){

    pushdown(now);

    while(now!=dst){

      if(now->pre==dst){

        if(dst->son[0]==now) rotate(now,1);

        else rotate(now,0);

        break;

      }

      nodep fa=now->pre,gfa=fa->pre;

      if(gfa->son[0]==fa){

        if(fa->son[0]==now) {rotate(fa,1);rotate(now,1);}

        else {rotate(now,0);rotate(now,1);}

      }else {

        if(fa->son[1]==now) {rotate(fa,0);rotate(now,0);}

        else {rotate(now,1);rotate(now,0);}

      }

      if(gfa==dst) break;

      pushup(now);

    }

    pushup(now);

  }

  void find(int k,nodep fa){

    int tmp;

    nodep t=root;

    while (1) {

      pushdown(t);

      tmp=getsize(t->son[0]);

      if (k==tmp+1) break;

      if (k<=tmp) t=t->son[0];

      else {

        k-=tmp+1,t=t->son[1];

      }

    }

    pushdown(t);

    splay(t, fa);

  }

  void findseg(int s,int t){

    find(s,root);

    find(t+2,root->son[1]);

  }

  void insert(int pos,ll val){

    findseg(pos+1,pos);

    nodep now,fa=root->son[1];

    pushdown(root);

    pushdown(fa);

    if(!stk.empty()){

      now=stk.top();

      stk.pop();

    }else now=&node[cnt++];

    now->init(val);

    now->son[1]=fa;

    fa->pre=now;

    root->son[1]=now;

    now->pre=root;

    splay(fa,root);

  }

  void add(int s,int t,ll val){

    findseg(s,t);

    nodep now = root->son[1]->son[0];

    pushdown(now);

    pushup(now);

    now->mn+=val;

    now->tag+=val;

    splay(now,root);

  }

  void reverse(int s,int t){

    findseg(s,t);

    root->son[1]->son[0]->rev^=1;

    nodep now=root->son[1]->son[0];

    splay(now,root);

  }

  void revolve(int s,int t,int len){

    nodep x,y;

    findseg(s,t);

    find(t+1-len,root->son[1]->son[0]);

    x=root->son[1]->son[0];

    pushdown(x);

    y=x->son[1];

    x->son[1]=NULL;

    find(s+1,root->son[1]->son[0]);

    x=root->son[1]->son[0];

    pushdown(x);

    x->son[0]=y;

    y->pre=x;

    splay(y,root);

  }

  ll getmin(int s,int t) {

    findseg(s,t);

    nodep now=root->son[1];

    pushdown(now);

    now=now->son[0];

    pushdown(now);

    pushup(now);

    return now->mn;

  }

  void erase(int pos){

    findseg(pos, pos);

    pushdown(root->son[1]);

    stk.push(root->son[1]->son[0]);

    root->son[1]->son[0] = NULL;

    nodep now = root->son[1];

    splay(now,root);

  }

  splaytree(ll*a,int n){

		cnt=0;

		node.resize(maxn);

    root=&node[cnt++];

    root->init(INF);

    root->son[1]=&node[cnt++];

    root->son[1]->init(INF);

    while (!stk.empty()) stk.pop();

    rep(i,0,n-1) insert(i, a[i]);

  }

};

ll v[maxn];

int main() {

  int n, m;

  scanf("%d", &n);

  rep(i,0,n-1) scanf("%lld",&v[i]);

  scanf("%d", &m);

  splaytree tree(v, n);

  while (m--) {

    char s[50];

    scanf("%s",s);

    if (s[0]=='A') {

      int l, r, d;

      scanf("%d%d%d",&l,&r,&d);

      tree.add(l,r,d);

    }

    if (s[0]=='R') {

      int l, r;

      scanf("%d%d",&l,&r);

      if (s[3]=='E') tree.reverse(l,r);

      else {

        int k;

        scanf("%d",&k);

        int tn=r-l+1;

        k=(k%tn+tn)%tn;

        if (l==r||k==0) continue;

        tree.revolve(l,r,k);

      }

    }

    if (s[0]=='I') {

      int x, d;

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

      tree.insert(x,d);

    }

    if (s[0]=='D') {

      int x;

      scanf("%d",&x);

      tree.erase(x);

    }

    if (s[0]=='M') {

      int l, r;

      scanf("%d%d",&l,&r);

      printf("%lld\n",tree.getmin(l,r));

    }

  }

  return 0;

}

2.不用stack

#include <iostream>

#include <vector>

#define ll long long

#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)

using namespace std;

const int maxn=1e6+10,maxm=2e6+10;

const int INF=0x3f3f3f3f;

class splaytree{

	public:

	struct splaynode{

		splaynode *son[2],*pre;

		ll val,tag,mn;

		int size,rev;

		void init(ll x){

			pre=son[1]=son[0]=NULL;

			mn=val=x;

			tag=rev=0;

			size=1;

		}

		void add(ll x){tag+=x,mn+=x;}

	};

	typedef struct splaynode* nodep;

  int cnt;

  nodep root;

	vector<splaynode> node;

  int getsize(nodep x){return x?x->size:0;}

  void pushdown(nodep now){

    if(!now) return ;

    if(now->tag){

      ll tag=now->tag;

      now->val+=tag;

      if(now->son[0]) now->son[0]->add(tag);

      if(now->son[1]) now->son[1]->add(tag);

      now->tag=0;

    }

    if(now->rev){

      swap(now->son[0],now->son[1]);

      now->rev=0;

      if(now->son[0]) now->son[0]->rev^=1;

      if(now->son[1]) now->son[1]->rev^=1;

    }

  }

  void pushup(nodep now){

    if(!now) return ;

    now->size=1,now->mn=now->val;

    if(now->son[0]) {

      now->mn=min(now->mn,now->son[0]->mn);

      now->size+=now->son[0]->size;

    }

    if(now->son[1]){

      now->mn=min(now->mn,now->son[1]->mn);

      now->size+=now->son[1]->size;

    }

  }

  void rotate(nodep now,int d){

    nodep fa=now->pre;

    pushdown(fa);

    pushdown(now);

    pushdown(now->son[d]);

    fa->son[!d]=now->son[d];

    if(now->son[d]) now->son[d]->pre=fa;

    now->pre=fa->pre;

    if(fa->pre){

      if(fa->pre->son[0]==fa) fa->pre->son[0]=now;

      else fa->pre->son[1]=now;

    }else root=now;

    now->son[d]=fa;

    fa->pre=now;

    pushup(fa);

  }

  void splay(nodep now,nodep dst){

    pushdown(now);

    while(now!=dst){

      if(now->pre==dst){

        if(dst->son[0]==now) rotate(now,1);

        else rotate(now,0);

        break;

      }

      nodep fa=now->pre,gfa=fa->pre;

      if(gfa->son[0]==fa){

        if(fa->son[0]==now) {rotate(fa,1);rotate(now,1);}

        else {rotate(now,0);rotate(now,1);}

      }else {

        if(fa->son[1]==now) {rotate(fa,0);rotate(now,0);}

        else {rotate(now,1);rotate(now,0);}

      }

      if(gfa==dst) break;

      pushup(now);

    }

    pushup(now);

  }

  void find(int k,nodep fa){

    int tmp;

    nodep t=root;

    while (1) {

      pushdown(t);

      tmp=getsize(t->son[0]);

      if (k==tmp+1) break;

      if (k<=tmp) t=t->son[0];

      else {

        k-=tmp+1,t=t->son[1];

      }

    }

    pushdown(t);

    splay(t, fa);

  }

  void findseg(int s,int t){

    find(s,root);

    find(t+2,root->son[1]);

  }

  void insert(int pos,ll val){

    findseg(pos+1,pos);

    nodep now,fa=root->son[1];

    pushdown(root);

    pushdown(fa);

    now=&node[cnt++];

    now->init(val);

    now->son[1]=fa;

    fa->pre=now;

    root->son[1]=now;

    now->pre=root;

    splay(fa,root);

  }

  void add(int s,int t,ll val){

    findseg(s,t);

    nodep now = root->son[1]->son[0];

    pushdown(now);

    pushup(now);

    now->mn+=val;

    now->tag+=val;

    splay(now,root);

  }

  void reverse(int s,int t){

    findseg(s,t);

    root->son[1]->son[0]->rev^=1;

    nodep now=root->son[1]->son[0];

    splay(now,root);

  }

  void revolve(int s,int t,int len){

    nodep x,y;

    findseg(s,t);

    find(t+1-len,root->son[1]->son[0]);

    x=root->son[1]->son[0];

    pushdown(x);

    y=x->son[1];

    x->son[1]=NULL;

    find(s+1,root->son[1]->son[0]);

    x=root->son[1]->son[0];

    pushdown(x);

    x->son[0]=y;

    y->pre=x;

    splay(y,root);

  }

  ll getmin(int s,int t) {

    findseg(s,t);

    nodep now=root->son[1];

    pushdown(now);

    now=now->son[0];

    pushdown(now);

    pushup(now);

    return now->mn;

  }

  void erase(int pos){

    findseg(pos, pos);

    pushdown(root->son[1]);

    root->son[1]->son[0] = NULL;

    nodep now = root->son[1];

    splay(now,root);

  }

  splaytree(vector<int> num,int n){

  	cnt=0;

		node.resize(n+7);

    root=&node[cnt++];

    root->init(INF);

    root->son[1]=&node[cnt++];

    root->son[1]->init(INF);

    int size=num.size();

		rep(i,0,size-1) insert(i, num[i]);

  }

};

int main() {

	ios::sync_with_stdio(false),cin.tie(0);

  int n,m;

  cin>>n;

  vector<int> v(n);

  rep(i,0,n-1) cin>>v[i];

  cin>>m;

  splaytree tree(v,n+m);

  while (m--) {

    string s;

    cin>>s;

    if (s[0]=='A') {

      int l,r,d;cin>>l>>r>>d;

      tree.add(l,r,d);

    }

    if (s[0]=='R') {

      int l,r;cin>>l>>r;

      if (s[3]=='E') tree.reverse(l,r);

      else {

        int k;cin>>k;

        int tn=r-l+1;

        k=(k%tn+tn)%tn;

        if (l==r||k==0) continue;

        tree.revolve(l,r,k);

      }

    }

    if (s[0]=='I') {

      int x,d;cin>>x>>d;

      tree.insert(x,d);

    }

    if (s[0]=='D') {

      int x;cin>>x;

      tree.erase(x);

    }

    if (s[0]=='M') {

      int l,r;cin>>l>>r;

      cout<<tree.getmin(l,r)<<endl;

    }

  }

  return 0;

}

　　

相关文章