智乃酱的cube

C++(g++ 7.5.0) 解法, 执行用时: 1994ms, 内存消耗: 24008K, 提交时间: 2023-08-12 17:12:41

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define fi first
#define sc second
#define endl '\n'
#define debug(x) cout << "debug:x " << x << endl
using ll = long long;
using PII = pair<ll, int>;
using PIII = tuple<int, int, int>;

const int maxn = 5e5 + 10;
const int maxm = 3e6 + 10; 
const ll INF = 9e18;
const int mod = 1e9 + 7;
int n, m, k, q;

struct Node {
    int l, r;
    ll s[3], len[3], v;
    ll lazy[3];
}tr[maxn * 4];

void pushup(int u) {
    for (int i = 0; i < 3; i++) {
        tr[u].s[i] = (tr[u << 1].s[i] + tr[u << 1 | 1].s[i]) % mod;
        tr[u].len[i] = (tr[u << 1].len[i] + tr[u << 1 | 1].len[i]) % mod;
    }
    tr[u].v = (tr[u << 1].v + tr[u << 1 | 1].v) % mod;
}

void update(int u, ll x, int op) {
    tr[u].v = (tr[u].v + tr[u].s[op] * x) % mod;
    for (int i = 0; i < 3; i++) {
        if (i != op) tr[u].s[i] = (tr[u].s[i] + tr[u].len[3 - op - i] * x) % mod;
    }
    tr[u].len[op] = (tr[u].len[op] + x * (tr[u].r - tr[u].l + 1)) % mod;
    tr[u].lazy[op] = (tr[u].lazy[op] + x) % mod;
}

void pushdown(int u) {
    for (int i = 0; i < 3; i++) {
        if (tr[u].lazy[i]) {
            update(u << 1, tr[u].lazy[i], i);
            update(u << 1 | 1, tr[u].lazy[i], i);
            tr[u].lazy[i] = 0;
        }
    }
}

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l == r) {
        for (int i = 0; i < 3; i++) {
            tr[u].s[i] = tr[u].len[i] = 1;
        }
        tr[u].v = 1;
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int l, int r, ll x, int op) {
    if (tr[u].l >= l && tr[u].r <= r) {
        update(u, x, op);
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modify(u << 1, l, r, x, op);
    if (r > mid) modify(u << 1 | 1, l, r, x, op);
    pushup(u);
}

ll query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) {
        return tr[u].v;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    ll ans = 0;
    if (l <= mid) ans = (ans + query(u << 1, l, r)) % mod;
    if (r > mid) ans = (ans + query(u << 1 | 1, l, r)) % mod;
    return ans;
}

void IndianaNoNNnnn() {
    cin >> n >> m;
    build(1, 1, n);
    while (m--) {
        char op;
        int l, r;
        cin >> op >> l >> r;
        if (op == 'q') {
            cout << query(1, l, r) << endl;
        }
        else {
            ll x;
            cin >> x;
            if (op == 'x') modify(1, l, r, x, 0);
            else if (op == 'y') modify(1, l, r, x, 1);
            else modify(1, l, r, x, 2);
        }
    }
}                    

  
int main() {
    IOS; 
    int w_ = 1;
  //  cin >> w_;
    while (w_--) IndianaNoNNnnn();
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 1682ms, 内存消耗: 13700K, 提交时间: 2023-04-06 18:39:32

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+9,P=1e9+7;
int n,m;
struct node{
	int l,r;
	int x,y,z,xy,yz,xz,xyz;
	int ax,ay,az;
}tr[N*4];
void pushup(int u){
	node &t=tr[u],&l=tr[u<<1],&r=tr[u<<1|1];
	t.x=(l.x+r.x)%P;
	t.y=(l.y+r.y)%P;
	t.z=(l.z+r.z)%P;
	t.xy=(l.xy+r.xy)%P;
	t.yz=(l.yz+r.yz)%P;
	t.xz=(l.xz+r.xz)%P;
	t.xyz=(l.xyz+r.xyz)%P;
}
void work(node &t,int ax,int ay,int az){
	int len=t.r-t.l+1;
	t.xyz=(t.xyz+(LL)ax*t.yz%P+(LL)ay*t.xz%P+(LL)az*t.xy%P+(LL)ax*ay%P*t.z%P+(LL)ax*az%P*t.y%P+(LL)ay*az%P*t.x%P+(LL)ax*ay%P*az%P*len%P)%P;
	t.xy=(t.xy+(LL)ax*t.y%P+(LL)ay*t.x+(LL)ax*ay%P*len)%P;
	t.yz=(t.yz+(LL)ay*t.z%P+(LL)az*t.y+(LL)ay*az%P*len)%P;
	t.xz=(t.xz+(LL)ax*t.z%P+(LL)az*t.x+(LL)ax*az%P*len)%P;
	t.x=(t.x+(LL)len*ax)%P;
	t.y=(t.y+(LL)len*ay)%P;
	t.z=(t.z+(LL)len*az)%P;
	t.ax=(t.ax+ax)%P;
	t.ay=(t.ay+ay)%P;
	t.az=(t.az+az)%P;
}
void pushdown(int u){
	work(tr[u<<1],tr[u].ax,tr[u].ay,tr[u].az);
	work(tr[u<<1|1],tr[u].ax,tr[u].ay,tr[u].az);
	tr[u].ax=tr[u].ay=tr[u].az=0;
}
void build(int u,int l,int r){
	tr[u]=(node){l,r,1,1,1,1,1,1,1,0,0,0};
	if(l!=r){
		int mid=l+r>>1;
		build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
	}
} 
void modify(int u,int l,int r,int ax,int ay,int az){
	if(tr[u].l>=l&&tr[u].r<=r) work(tr[u],ax,ay,az);
	else{
		pushdown(u);
		int mid=tr[u].l+tr[u].r>>1;
		if(l<=mid) modify(u<<1,l,r,ax,ay,az);
		if(r>mid) modify(u<<1|1,l,r,ax,ay,az);
		pushup(u);
	}
}
int query(int u,int l,int r){
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u].xyz;
	else{
		pushdown(u);
		int mid=tr[u].l+tr[u].r>>1,res=0;
		if(l<=mid) res=query(u<<1,l,r);
		if(r>mid) res=(res+query(u<<1|1,l,r))%P;
		return res;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	build(1,1,n);
	char op[2]; int l,r,a;
	while(m--){
		scanf("%s",op);
		if(*op=='q'){
			scanf("%d%d",&l,&r);
            int t=query(1,l,r);
			printf("%d\n",t);
		}
		else{
			scanf("%d%d%d",&l,&r,&a);
			if(*op=='x') modify(1,l,r,a,0,0);
			else if(*op=='y') modify(1,l,r,0,a,0);
			else modify(1,l,r,0,0,a);
		}
	}
	return 0;
}

详情