题意:给你一串灯,灯有开的有关的,也有自己的数值,可进行的操作有:在某个灯后添加新的灯、移除某盏灯、把灯打开或关闭、更新灯的值。有若干询问,问某一区间内的灯的公约数,没有则输出-1。主要是数据比较大,操作多,容易TLE
浙大月赛的题目,天真的我都用链表写了。。。然后内存分配搓了一运行就崩溃。后来百度得知是伸展树(从没听过),用数组和链表做的话,可能都有样例会卡时间造成TLE,百度了一个模板,暂时当作模板用,等多做几道伸展树再搞自己的模板
#include<iostream> #include<cstdio> #include<cmath> #include<cctype> #include<cstring> using namespace std; #define MAXN 300005 #define lson x->ch[0] #define rson x->ch[1] #define ket (root->ch[1]->ch[0]) int gcd(int a,int b){ return b?gcd(b,a%b):a; } struct Node{ int val, sz, id, on, G[2]; Node *ch[2], *pnt;//左右儿子和父亲 void up(){ sz = ch[0]->sz + ch[1]->sz + 1; G[on] = gcd(val,gcd(ch[0]->G[on],ch[1]->G[on])); G[!on] = gcd(ch[0]->G[!on],ch[1]->G[!on]); } }; struct Splaytree{//伸展树结构体类型 int top; Node *root,*null; Node node[MAXN]; void Rotate(Node *x, int c){ Node *y = x->pnt; y->ch[!c] = x->ch[c]; if (x->ch[c] != null) x->ch[c]->pnt = y; x->pnt = y->pnt; if (y->pnt != null) y->pnt->ch[y->pnt->ch[1] == y] = x; x->ch[c] = y; y->pnt = x; y->up(); } void Splay(Node *x, Node *go){//将x伸展到go的儿子位置处 while (x->pnt != go){ if(x->pnt->pnt == go) Rotate(x,x->pnt->ch[0]==x); else{ Node *y = x->pnt,*z = y->pnt; int f = z->ch[1] == y; if(y->ch[f] == x) Rotate(y,!f); else Rotate(x,f); Rotate(x,!f); } } x->up(); if(go == null) root = x; } void RTO(int k,Node *go){ Node *x = root; while(lson->sz != k){ if(lson->sz > k) x = lson; else{ k -= lson->sz + 1; x = rson; } } Splay(x,go); } int a[MAXN],b[MAXN]; Node *newnode(int val,int on,Node *f){ Node *x = &node[++top]; x->id = top; x->sz = 1; lson = rson = null; x->on = on; x->val = x->G[on] = val; x->G[!on] = 0; x->pnt = f; return x; } Node *build(int l,int r,Node *f){ if(l > r) return null; int mid = (l + r) / 2; Node *x = newnode(a[mid],b[mid],f); lson = build(l,mid-1,x); rson = build(mid+1,r,x); x->up(); return x; } void init(int n){ null = &node[0]; null->sz = null->G[0] = null->G[0] = null->val = 0; top = 0; root = newnode(0,0,null); root->ch[1] = newnode(0,0,root); for(int i = 0;i<n;i++) scanf("%d%d",&a[i],&b[i]); ket = build(0,n-1,root->ch[1]); root->ch[1]->up(); root->up(); } void Get(int l,int r){ RTO(l-1,null); RTO(r+1,root); } void Query(){ int l,r,on; scanf("%d%d%d",&l,&r,&on); Get(l,r); int ans = ket->G[on]; if(!ans) printf("-1\n"); else printf("%d\n",ans); } void Insert(){//插入一个值 int i,val,on; scanf("%d%d%d",&i,&val,&on); RTO(i,null); RTO(i+1,root); ket = newnode(val,on,root->ch[1]); root->ch[1]->up(); root->up(); } void Delete(){//删除一个值 int i; scanf("%d",&i); Get(i,i); ket = null; root->ch[1]->up(); root->up(); } void RR(){ int i; scanf("%d",&i); Get(i,i); ket->on ^= 1; swap(ket->G[0],ket->G[1]); root->ch[1]->up(); root->up(); } void Modify(){ int i,v; scanf("%d%d",&i,&v); Get(i,i); ket->val = ket->G[ket->on] = v; root->ch[1]->up(); root->up(); } }sp; int main(){ int n,q,i; while(scanf("%d%d",&n,&q)!=EOF){ sp.init(n); for(i=0;i<q;i++){ char c[5]; scanf("%s",c); if(c[0] == 'Q') sp.Query(); else if(c[0] == 'I') sp.Insert(); else if(c[0] == 'D') sp.Delete(); else if(c[0] == 'R') sp.RR(); else sp.Modify(); } } return 0; }