Mn Zn 珂朵莉求调
  • 板块P5350 序列
  • 楼主cjwdyzxfblzs
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/6/27 17:24
  • 上次更新2023/11/3 12:18:50
查看原帖
Mn Zn 珂朵莉求调
817044
cjwdyzxfblzs楼主2023/6/27 17:24

不知道为什么全RE了,但是本地测样例可以过的欸

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N = 1e6;
const int INF = 1e9 + 7;
int n, m;
struct node
{
    int l, r; 
    mutable int v;
    node() {}
    node(int l, int r = 0, int v = 0) : l(l), r(r), v(v) {}
    bool operator<(const node &O)const { return l < O.l; }
}a[N], b[N];
set<node> tree;
set<node>::iterator split(int pos)
{
    set<node>::iterator it = tree.lower_bound(node(pos));
    if (it != tree.end() and it->l == pos)
        return it;
    it -- ;
    if (it->r < pos) return tree.end();
    int l = it->l, r = it->r, v = it->v;
    tree.erase(it);
    tree.insert(node(l, pos - 1, v));
    return tree.insert(node(pos, r, v)).first;
}
inline void add(int l, int r, int v)
{
    set<node>::iterator end = split(r + 1), begin = split(l);
    for (set<node>::iterator it = begin; it != end; it ++ )
        (it->v += v) %= INF;
}
inline void assign(int l, int r, int v)
{
    set<node>::iterator end = split(r + 1), begin = split(l);
    tree.erase(begin, end);
    tree.insert(node(l, r, v));
}
inline int sum(int l, int r)
{
    set<node>::iterator end = split(r + 1), begin = split(l);
    int ans = 0;
    for (set<node>::iterator it = begin; it != end; it ++ )
        (ans += it->v * (it->r - it->l + 1)) %= INF;
    return ans % INF;
}
inline void clone(int l, int r, int L, int R)
{
    set<node>::iterator end_1 = split(r + 1), begin_1 = split(l);
    int len = 0;
    for (set<node>::iterator it = begin_1; it != end_1; it ++ )
        a[ ++ len].l = it->l, a[len].r = it->r, a[len].v = it->v;
    set<node>::iterator end_2 = split(R + 1), begin_2 = split(L);
    tree.erase(begin_2, end_2);
    for (int i = 1; i <= len; i ++ )
        tree.insert(node(a[i].l - l + L, a[i].r - l + L, a[i].v));
}
inline void swap(int a, int b) { a ^= b, b ^= a, a ^= b; }
inline void Swap(int l, int r, int L, int R)
{
    if (l > L) { swap(l, L); swap(r, R); }
    int len1 = 0, len2 = 0;
    set<node>::iterator end_1 = split(r + 1), begin_1 = split(l);
    for (set<node>::iterator it = begin_1; it != end_1; it ++ )
    {
        a[ ++ len1].l = it->l;
        a[len1].r = it->r;
        a[len1].v = it->v;
    }
    tree.erase(begin_1, end_1);
    set<node>::iterator end_2 = split(R + 1), begin_2 = split(L);
    for (set<node>::iterator it = begin_2; it != end_2; it ++ )
    {
        b[ ++ len2].l = it->l;
        b[len2].r = it->r;
        b[len2].v = it->v;
    }
    tree.erase(begin_2, end_2);
    for (int i = 1; i <= len2; i ++ ) 
        tree.insert(node(l + b[i].l - L, l + b[i].r - L, b[i].v));
    for (int i = 1; i <= len1; i ++ )
        tree.insert(node(L + a[i].l - l, L + a[i].r - l, a[i].v));
}
inline void reverse(int l, int r)
{
    if (l > r) swap(l, r);
    set<node>::iterator end = split(r + 1), begin = split(l);
    int len = 0;
    for (set<node>::iterator it = begin; it != end; it ++ )
    {
        a[ ++ len].l = it->l;
        a[len].r = it->r;
        a[len].v = it->v;
    }
    tree.erase(begin, end);
    for (int i = 1; i <= len; i ++ )
        tree.insert(node(r - a[i].r + l, r - a[i].r + l, a[i].v));
}
signed main()
{
    n = read(), m = read();
    for (int i = 1, x; i <= n; i ++ )
    {
        x = read();
        tree.insert(node(i, i, x));
    }
    for (int i = 1; i <= m; i ++ )
    {
        int op = read();
        if (op == 1)
        {
            int l = read(), r = read();
            if (l > r) swap(l, r);
            cout << sum(l, r) << endl;
        }
        else if (op == 2)
        {
            int l = read(), r = read(), val = read();
            if (l > r) swap(l, r);
            assign(l, r, val);
        }
        else if (op == 3)
        {   
            int l = read(), r = read(), val = read();
            if (l > r) swap(l, r);
            add(l, r, val);
        }
        else if (op == 4)
        {
            int l = read(), r = read(), L = read(), R = read();
            if (l > r) swap(l, r);
            if (L > R) swap(L, R);
            clone(l, r, L, R);
        }
        else if (op == 5)
        {
            int l = read(), r = read(), L = read(), R = read();
            if (l > r) swap(l, r);
            if (L > R) swap(L, R);
            Swap(l, r, L, R);
        }
        else 
        {
            int l = read(), r = read();
            if (l > r) swap(l, r);
            reverse(l, r);
        }
    }
    for (auto V : tree)
    {
        for (int i = V.l; i <= V.r; i ++ )
            cout << V.v % INF << " ";
    }
    return 0;
}

2023/6/27 17:24
加载中...