202012-5 星际旅行

2024-04-14 16:38

文章标签 旅行星际 202012

本文主要是介绍202012-5 星际旅行，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

202012-5 星际旅行

80分做法，因为N太大了，太菜的我不知道如何处理
我的方法： $x, y, z$ 轴分别开一颗线段树，然后就套用线段树，区间加，区间乘，然后这里有个线段树互相交换节点，需要先全部pushdown之后再交换，交换完成之后还要pushup

//80分做法
#include <stdio.h>
#include <iostream>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll maxn = 1e6+10;ll N,M;
const ll mod = 1e9 + 7;
struct node{ll l,r,lson,rson;ll add,mul,sum;
}tr[maxn*4];ll idx;
ll rtx,rty,rtz;
struct Seg{void pushup(node &U,node& L,node& R){U.sum = (L.sum + R.sum)%mod;}ll build(ll l,ll r){tr[++idx] = {l,r,-1,-1,0,1,0};ll id = idx;if(l == r){return idx;}else{ll mid = (l+r)>>1;tr[id].lson = build(l,mid);tr[id].rson = build(mid+1,r);pushup(tr[id],tr[tr[id].l],tr[tr[id].r]);}return id;}void pushdown(node &U,node &L,node &R){L.sum = (L.sum * U.mul%mod + (L.r - L.l + 1) * U.add%mod) %mod;R.sum = (R.sum * U.mul%mod + (R.r - R.l + 1) * U.add%mod) %mod;L.add = (L.add * U.mul %mod + U.add)%mod;R.add = (R.add * U.mul %mod + U.add)%mod;L.mul = (L.mul * U.mul)%mod;R.mul = (R.mul * U.mul)%mod;U.add = 0;U.mul = 1;}void add(ll u,ll l,ll r,ll v){if(l <= tr[u].l && tr[u].r <= r){tr[u].sum = (tr[u].sum + v * (tr[u].r-tr[u].l+1)%mod) %mod;tr[u].add = (tr[u].add + v )%mod;}else{pushdown(tr[u],tr[tr[u].lson],tr[tr[u].rson]);ll mid = (tr[u].l + tr[u].r)>>1;if(l <= mid) add(tr[u].lson,l,r,v);if(r > mid) add(tr[u].rson,l,r,v);pushup(tr[u],tr[tr[u].lson],tr[tr[u].rson]);}}void mul(ll u,ll l,ll r,ll v){if(l<= tr[u].l && tr[u].r <= r){tr[u].sum = (tr[u].sum * v)%mod;tr[u].mul = (tr[u].mul * v)%mod;tr[u].add = (tr[u].add * v)%mod;}else{pushdown(tr[u],tr[tr[u].lson],tr[tr[u].rson]);ll mid = (tr[u].l + tr[u].r)>>1;if(l<=mid) mul(tr[u].lson,l,r,v);if(r>mid) mul(tr[u].rson,l,r,v);pushup(tr[u],tr[tr[u].lson],tr[tr[u].rson]);}}node query(ll u,ll l,ll r){if(l <= tr[u].l && tr[u].r <= r){return tr[u];}else{pushdown(tr[u],tr[tr[u].lson],tr[tr[u].rson]);ll mid = (tr[u].l + tr[u].r)>>1;if(r<=mid) return query(tr[u].lson,l,r);else if(l>mid) return query(tr[u].rson,l,r);else{node ans1 = query(tr[u].lson,l,r);node ans2 = query(tr[u].rson,l,r);node ans;pushup(ans,ans1,ans2);return ans;}}}void find(vector<ll> &ve,ll u,ll l,ll r){if(l<= tr[u].l && tr[u].r <= r){ve.push_back(u);}else{pushdown(tr[u],tr[tr[u].lson],tr[tr[u].rson]);ll mid = (tr[u].l+tr[u].r)>>1;if(l<=mid) find(ve,tr[u].lson,l,r);if(r>mid) find(ve,tr[u].rson,l,r);pushup(tr[u],tr[tr[u].lson],tr[tr[u].rson]);}}void change(ll l,ll r){vector<ll> vex,vey,vez;find(vex,rtx,l,r);find(vey,rty,l,r);find(vez,rtz,l,r);for(ll i = 0;i<vex.size();i++){ll x = vex[i],y = vey[i],z = vez[i];swap(tr[x],tr[z]);swap(tr[x],tr[y]);}find(vex,rtx,l,r);find(vey,rty,l,r);find(vez,rtz,l,r);}
}seg;int main(){cin>>N>>M;rtx = seg.build(1,N);rty = seg.build(1,N);rtz = seg.build(1,N);while(M--){ll op,l,r;scanf("%lld %lld %lld",&op,&l,&r);if(op == 1){ll a,b,c;scanf("%lld %lld %lld",&a,&b,&c);seg.add(rtx,l,r,a);seg.add(rty,l,r,b);seg.add(rtz,l,r,c);}if(op == 2){ll k;scanf("%lld",&k);seg.mul(rtx,l,r,k);seg.mul(rty,l,r,k);seg.mul(rtz,l,r,k);}if(op == 3){seg.change(l,r);}if(op == 4){ll sumx = seg.query(rtx,l,r).sum; \\cout<<sumx<<'\n';ll sumy = seg.query(rty,l,r).sum; \\cout<<sumy<<'\n';ll sumz = seg.query(rtz,l,r).sum; \\cout<<sumz<<'\n';printf("%lld\n",(sumx*sumx%mod + sumy*sumy%mod + sumz*sumz%mod)%mod);}}return 0;
}