//Let's join Kaede Takagaki Fan Club !! #include #include #include using namespace std; typedef long long ll; typedef pair P; typedef pair P1; typedef pair P2; #define pu push #define pb push_back #define mp make_pair #define eps 1e-7 #define INF 1000000000 #define fi first #define sc second #define rep(i,x) for(int i=0;i void dmp(T a){ rep(i,a.size()) cout << a[i] << " "; cout << endl; } template bool chmax(T&a, T b){ if(a < b){ a = b; return 1; } return 0; } template bool chmin(T&a, T b){ if(a > b){ a = b; return 1; } return 0; } template void g(T &a){ cin >> a; } template void o(const T &a,bool space=false){ cout << a << (space?' ':'\n'); } //ios::sync_with_stdio(false); const ll mod = 1000000007;//998244353 template void add(T&a,T b){ a+=b; if(a >= mod) a-=mod; } struct LinkCutTree{ struct dat { int cnt1; ll sum, sum1, sum2; void rv(){ swap(sum1, sum2); } }; struct node{ node *p,*l,*r; int id, rev; dat D, L, S; multiset>L_sz; node(int i, int c, int w) : l(0), r(0), p(0), id(i), rev(0) { D = S = {c, w, w, w}; L = {0, 0, 0, 0}; L_sz.clear(); } //このノードはsplay木の根? (=今いるパスの最上頂点?) bool is_root(){ return !p || (p->l != this && p->r != this); } }; //右回転 void rotr(node *n){ node *q = n->p, *g = q->p; if((q->l = n->r)) n->r->p = q; n->r = q; q->p = n; update(q); update(n); if((n->p = g)){ if(g->l == q) g->l = n; else if(g->r == q) g->r = n; else{ g->L_sz.erase(mp(n->D.cnt1, q->id)); g->L_sz.insert(mp(n->D.cnt1, n->id)); } update(g); } } //左回転 void rotl(node *n){ node *q = n->p, *g = q->p; if((q->r = n->l)) n->l->p = q; n->l = q; q->p = n; update(q); update(n); if((n->p = g)){ if(g->l == q) g->l = n; else if(g->r == q) g->r = n; else{ g->L_sz.erase(mp(n->D.cnt1, q->id)); g->L_sz.insert(mp(n->D.cnt1, n->id)); } update(g); } } //スプレー操作 void splay(node *n){ push(n); while(!n->is_root()){ node *q = n->p; //自分の親がroot、zig if(q->is_root()){ push(q); push(n); if(q->l == n){ rotr(n); } else{ rotl(n); } } else{ node *r = q->p; push(r); push(q); push(n); if(r->l == q){ if(q->l == n){ //zig-zig rotr(q); rotr(n); } else{ //zig-zag rotl(n); rotr(n); } } else{ if(q->r == n){ //zig-zig rotl(q); rotl(n); } else{ //zig-zag rotr(n); rotl(n); } } } } } vectorpool; //本質 //xから根までのパスを形成 node *expose(node *x){ node *rr = (node *)NULL; for(node *pp = x;pp;pp = pp->p){ //今いるところをsplay splay(pp); //右にさっきまでの木を繋げる if(pp->r){ pp->L.cnt1 += pp->r->D.cnt1; pp->L.sum1 += pp->r->D.sum1; pp->L_sz.insert(mp(pp->r->D.cnt1, pp->r->id)); } pp->r = rr; if(pp->r){ pp->L.cnt1 -= pp->r->D.cnt1; pp->L.sum1 -= pp->r->D.sum1; pp->L_sz.erase(mp(pp->r->D.cnt1, pp->r->id)); } //覚えておく update(pp); rr = pp; } splay(x); return rr; } node *find_root(node *n){ if(!n) return (node*)NULL; while(1){ push(n); if(n->r) n = n->r; else return n; } } node *cut(node *c){ expose(c); node *p = c->l; c->l->p = NULL; c->l = NULL; update(c); return find_root(p); } void link(node *c, node *p){ expose(c); expose(p); c->p = p; p->r = c; update(p); } void push(node *n){ if(n->rev){ swap(n->l, n->r); if(n->l) n->l->rev ^= 1, n->l->D.rv(); if(n->r) n->r->rev ^= 1, n->r->D.rv(); n->rev = 0; } } void update(node *n){ push(n); n->D.cnt1 = (n->l?n->l->D.cnt1:0) + (n->r?n->r->D.cnt1:0) + n->L.cnt1 + n->S.cnt1; n->D.sum = (n->l?n->l->D.sum:0) + (n->r?n->r->D.sum:0) + n->S.sum; n->D.sum1 = 0; if(n->l) n->D.sum1 += n->l->D.sum1; if(n->r) n->D.sum1 += n->r->D.sum1 + 1LL*(n->S.sum+(n->l?n->l->D.sum:0)) * n->r->D.cnt1; if(n->S.cnt1) n->D.sum1 += 1LL*(n->S.sum+(n->l?n->l->D.sum:0)); n->D.sum1 += n->L.sum1 + 1LL*(n->S.sum+(n->l?n->l->D.sum:0)) * n->L.cnt1; n->D.sum2 = 0; if(n->l) n->D.sum2 += n->l->D.sum2 + 1LL*(n->S.sum+(n->r?n->r->D.sum:0)) * n->l->D.cnt1; if(n->r) n->D.sum2 += n->r->D.sum2; if(n->S.cnt1) n->D.sum2 += 1LL*(n->S.sum+(n->r?n->r->D.sum:0)); n->D.sum2 += n->L.sum1 + 1LL*(n->S.sum+(n->r?n->r->D.sum:0)) * n->L.cnt1; cout << n->id << " " << (n->l?n->l->id:-1) << " " << (n->r?n->r->id:-1) << " " << n->L.cnt1 << " " << n->L.sum1 << endl; } //非連結なら-1 int LCA(node *a,node *b){ if(a->id == b->id) return a->id; expose(a); node *ret = expose(b); if(a->p == (node*)NULL) return -1; else return ret->id; } int find(node *n, int sz){ pairmn = mp(8e18, -1); for(int i=1;i<=798;i++){ if(LCA(n, pool[i]) == -1) continue; evert(pool[i]); mn = min(mn, mp(pool[i]->D.sum1, i)); } cout << "ANSWER" << " " << mn.fi << " " << mn.sc << endl; return mn.sc; /*int lim = (sz+1)/2; while(1){ push(n); if(n->r && n->r->D.cnt1 >= lim) n = n->r; else if(n->l && n->D.cnt1 - n->l->D.cnt1 < lim){ lim -= (n->D.cnt1-n->l->D.cnt1); n = n->l; } else if(n->L_sz.size() && (*n->L_sz.begin()).fi >= (sz+1)/2){ lim = (sz+1)/2; n = pool[(*n->L_sz.begin()).sc]; } else return n->id; }*/ } void evert(node *n){ expose(n); cout << n->id <<"ID " << endl; cout << n->D.sum1 << " " << n->D.sum2 << endl; n->rev ^= 1; n->D.rv(); cout << n->D.sum1 << " " << n->D.sum2 << endl; } }kaede; int n, q; ll sum; int nxt = 100001; int main(){ scanf("%d%d",&n, &q); kaede.pool.resize(400005, new LinkCutTree::node(0, 0, 0)); repn(i, n) kaede.pool[i] = new LinkCutTree::node(i, 1, 0); rep(i, q){ int ty; scanf("%d",&ty); if(ty == 1){ int a, b, c; scanf("%d%d%d",&a,&b,&c); a = (a-1+sum)%n+1; b = (b-1+sum)%n+1; cout << a << " d " << b << endl; kaede.evert(kaede.pool[a]); cout << kaede.pool[a]->D.sum1 << endl; kaede.pool[nxt] = new LinkCutTree::node(nxt, 0, c); cout << kaede.pool[nxt]->D.sum1 << endl; kaede.link(kaede.pool[a], kaede.pool[nxt]); kaede.link(kaede.pool[nxt], kaede.pool[b]); nxt++; for(int i=1;i<=n;i++){ kaede.evert(kaede.pool[i]); cout << kaede.pool[i]->id << " = " << i << endl; cout << i << " " << kaede.pool[i]->D.sum1 << " " << kaede.pool[i]->D.cnt1 << " " << kaede.pool[i]->D.sum << endl; } } else if(ty == 2){ int a, b; scanf("%d%d",&a,&b); a = (a-1+sum)%n+1; b = (b-1+sum)%n+1; kaede.evert(kaede.pool[a]); auto *mid = kaede.cut(kaede.pool[b]); kaede.cut(mid); for(int i=1;i<=n;i++){ kaede.evert(kaede.pool[i]); cout << i << " " << kaede.pool[i]->D.sum1 << endl; } } else{ int a; scanf("%d",&a); a = (a-1+sum)%n+1; kaede.evert(kaede.pool[a]); kaede.pool[a]->S.cnt1 ^= 1; kaede.update(kaede.pool[a]); cout << kaede.pool[a]->D.cnt1 << " " << kaede.pool[a]->D.sum1 << " " << kaede.pool[a]->D.sum2 << endl; ll ans; if(kaede.pool[a]->D.cnt1 == 0){ ans = 0; } else{ int cent = kaede.find(kaede.pool[a], kaede.pool[a]->D.cnt1); kaede.evert(kaede.pool[cent]); ans = kaede.pool[cent]->D.sum1; } printf("%lld\n", ans); sum = (sum+ans)%n; } } }