求助(玄关)
  • 板块P5350 序列
  • 楼主xz001
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/17 18:38
  • 上次更新2023/11/17 20:16:39
查看原帖
求助(玄关)
674967
xz001楼主2023/11/17 18:38

又 WA 又 TLE 又 RE 0pts。求吊。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
struct node {
	int l, r;
	mutable int v;
	node () {
		l = 0, r = 0, v = 0;
	}
	node (int L, int R, int V) {
		l = L, r = R, v = V;
	}
	bool operator < (const node b) const {
		return l < b.l;
	}
};
const int N = 3e5 + 10;
set <node> s;
node t1[N], t2[N];
int cnt1, cnt2;
set <node> :: iterator split (int mid) {
	set <node> :: iterator it = s.lower_bound({mid, 0, 0});
	if (it != s.end() && it->l == mid) return it;
	-- it;
	int l = it->l, r = it->r, v = it->v;
	s.erase(it);
	s.insert({l, mid - 1, v});
	return s.insert({mid, r, v}).first;
}
void assign (int L, int R, int v) {
	set <node> :: iterator r = split(-~R), l = split(L);
	s.erase(l, r);
	s.insert({L, R, v});
	return;
}
void add (int L, int R, int v) {
	set <node> :: iterator r = split(-~R), l = split(L);
	for (set <node> :: iterator i = l; i != r; ++ i) {
		i->v += v;
	}
	return; 
}
int query (int L, int R) {
    set <node> :: iterator r = split(-~R), l = split(L);
	int ans = 0;
	for (set <node> :: iterator i = l; i != r; ++ i) {
		ans = (ans + i->v * (i->r - i->l + 1)) % mod;
	}
	return ans;	
}
void copy (int l1, int r1, int l2, int r2) {
	set <node> :: iterator l, r, ll, rr;
	if (r2 > r1) {
		rr = split(r2 + 1);
		ll = split(l2);
		r = split(r1 + 1);
		l = split(l1); 
	} else {
		r = split(r1 + 1);
		l = split(l1);
		rr = split(r2 + 1);
		ll = split(l2);
	}
	int cnt = l2 - l1;
	s.erase(ll, rr);
	for (set <node> :: iterator i = l; i != r; ++ i) {
		s.insert({i->l + cnt, i->r + cnt, i->v});
	}
	return;
}
void swap (int l1, int r1, int l2, int r2) {
	set <node> :: iterator l, r, ll, rr;
	if (r2 > r1) {
		rr = split(r2 + 1);
		ll = split(l2);
		r = split(r1 + 1);
		l = split(l1); 
	} else {
		r = split(r1 + 1);
		l = split(l1);
		rr = split(r2 + 1);
		ll = split(l2);
	}
	int cnt = l2 - l1;
	cnt1 = cnt2 = 0;
	for (set <node> :: iterator i = l; i != r; ++ i) {
		t1[ ++ cnt1] = *i;
	}
	for (set <node> :: iterator i = ll; i != rr; ++ i) {
		t2[ ++ cnt2] = *i;
	}
	s.erase(l, r);
	s.erase(ll, rr);
	for (int i = 1; i <= cnt1; ++ i) {
		s.insert({t1[i].l + cnt, t1[i].r + cnt, t1[i].v});
	}
	for (int i = 1; i <= cnt2; ++ i) {
		s.insert({t2[i].l - cnt, t2[i].r - cnt, t2[i].v});
	}
	return;
}
void reverse (int L, int R) {
	set <node> :: iterator r = split(R + 1), l = split(L);
	cnt1 = 0;
	for (set <node> :: iterator i = l; i != r; ++ i) {
		t1[ ++ cnt1] = *i;
	}
	s.erase(l, r);
	for (int i = 1; i <= cnt1; ++ i) {
		s.insert({L + R - t1[i].l, L + R - t1[i].r, t1[i].v});
	}
	return;
}
int n, m;
signed main() {
	scanf("%lld%lld", &n, &m);
	for (int i = 1, a; i <= n; ++ i) {
		scanf("%lld", &a);
		s.insert({i, i, a});
	}
	while (m -- ) {
		int op;
		scanf("%lld", &op);
		if (op == 1) {
			int l, r;
			scanf("%lld%lld", &l, &r);
			printf("%lld\n", query (l, r));
		} else if (op == 2) {
			int l, r, v;
			scanf("%lld%lld%lld", &l, &r, &v);
			assign (l, r, v);
		} else if (op == 3) {
			int l, r, v;
			scanf("%lld%lld%lld", &l, &r, &v);
			add (l, r, v);
		} else if (op == 4) {
			int l1, r1, l2, r2;
			scanf("%lld%lld%lld%lld", &l1, &r1, &l2, &r2);
			copy (l1, r1, l2, r2);
		} else if (op == 5) {
			int l1, r1, l2, r2;
			scanf("%lld%lld%lld%lld", &l1, &r1, &l2, &r2);
			swap(l1, r1, l2, r2);
		} else {
			int l, r;
			scanf("%lld%lld", &l, &r);
			reverse(l, r);
		}
	}
	for (int i = 1; i <= n; ++ i) {
		printf("%lld ", query (i, i));
	}
    return 0;
}

2023/11/17 18:38
加载中...