UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#213058#584. t3Origami_Tobiichi100949ms8404kbC++117.9kb2024-11-09 18:38:122024-11-09 23:02:04

answer

#include <bits/stdc++.h>
using namespace std;
namespace Octane
{
// non terrae plus ultra
#define OCTANE
#define BUFFER_SIZE 100000
#define ll long long
#define db double
#define ldb long double
    char ibuf[BUFFER_SIZE], obuf[BUFFER_SIZE];
    char *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#ifdef ONLINE_JUDGE
#define getchar() ((p1 == p2) and (p2 = (p1 = ibuf) + fread(ibuf, 1, BUFFER_SIZE, stdin), p1 == p2) ? (EOF) : (*p1++))
#define putchar(x) ((p3 == obuf + BUFFER_SIZE) && (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf), *p3++ = x)
#endif // fread in OJ, getchar in local

#define isdigit(ch) (ch > 47 && ch < 58)
#define isspace(ch) (ch < 33 && ch != EOF)

    const ll pow10[] = {
        (ll)1e0,
        (ll)1e1,
        (ll)1e2,
        (ll)1e3,
        (ll)1e4,
        (ll)1e5,
        (ll)1e6,
        (ll)1e7,
        (ll)1e8,
        (ll)1e9,
        (ll)1e10,
        (ll)1e11,
        (ll)1e12,
        (ll)1e13,
        (ll)1e14,
        (ll)1e15,
        (ll)1e16,
        (ll)1e17,
        (ll)1e18,
    };

    struct Octane_t
    {
        ~Octane_t()
        {
            fwrite(obuf, p3 - obuf, 1, stdout);
        }
        bool flag = false;
        operator bool()
        {
            return flag;
        }
    } io;

    template <typename T>
    inline T read()
    {
        T s = 0;
        int w = 1;
        char ch;
        while (ch = getchar(), !isdigit(ch) && (ch != EOF))
            if (ch == '-')
                w = -1;
        if (ch == EOF)
            return 0;
        while (isdigit(ch))
            s = s * 10 + ch - 48, ch = getchar();
        if (ch == '.')
        {
            ll flt = 0;
            int cnt = 0;
            while (ch = getchar(), isdigit(ch))
                if (cnt < 18)
                    flt = flt * 10 + ch - 48, cnt++;
            s += (db)flt / pow10[cnt];
        }
        return s *= w;
    }
    template <typename T>
    inline bool read(T &s)
    {
        s = 0;
        int w = 1;
        char ch;
        while (ch = getchar(), !isdigit(ch) && (ch != EOF))
            if (ch == '-')
                w = -1;
        if (ch == EOF)
            return false;
        while (isdigit(ch))
            s = s * 10 + ch - 48, ch = getchar();
        if (ch == '.')
        {
            ll flt = 0;
            int cnt = 0;
            while (ch = getchar(), isdigit(ch))
                if (cnt < 18)
                    flt = flt * 10 + ch - 48, cnt++;
            s += (db)flt / pow10[cnt];
        }
        return s *= w, true;
    }
    inline bool read(char &s)
    {
        while (s = getchar(), isspace(s))
            ;
        return s != EOF;
    }
    inline bool read(char *s)
    {
        char ch;
        while (ch = getchar(), isspace(ch))
            ;
        if (ch == EOF)
            return false;
        while (!isspace(ch))
            *s++ = ch, ch = getchar();
        *s = '\000';
        return true;
    }
    template <typename T>
    void print(T x)
    {
        static int t[20];
        int top = 0;
        if (x < 0)
            putchar('-'), x = -x;
        do
        {
            t[++top] = x % 10;
            x /= 10;
        } while (x);
        while (top)
            putchar(t[top--] + 48);
    }
    struct empty_type
    {
    };
    int pcs = 8;
    empty_type setpcs(int cnt)
    {
        return pcs = cnt, empty_type();
    }
    inline void print(empty_type x) {}
    inline void print(double x)
    {
        if (x < 0)
            putchar('-'), x = -x;
        x += 5.0 / pow10[pcs + 1];
        print((ll)(x));
        x -= (ll)(x);
        if (pcs != 0)
            putchar('.');
        for (int i = 1; i <= pcs; i++)
            x *= 10, putchar((int)x + '0'), x -= (int)x;
    }
    inline void print(float x)
    {
        if (x < 0)
            putchar('-'), x = -x;
        x += 5.0 / pow10[pcs + 1];
        print((ll)(x));
        x -= (ll)(x);
        if (pcs != 0)
            putchar('.');
        for (int i = 1; i <= pcs; i++)
            x *= 10, putchar((int)x + '0'), x -= (int)x;
    }
    inline void print(char x)
    {
        putchar(x);
    }
    inline void print(char *x)
    {
        for (int i = 0; x[i]; i++)
            putchar(x[i]);
    }
    inline void print(const char *x)
    {
        for (int i = 0; x[i]; i++)
            putchar(x[i]);
    }

// support for string
#ifdef _GLIBCXX_STRING
    inline bool read(std::string &s)
    {
        s = "";
        char ch;
        while (ch = getchar(), isspace(ch))
            ;
        if (ch == EOF)
            return false;
        while (!isspace(ch))
            s += ch, ch = getchar();
        return true;
    }
    inline void print(std::string x)
    {
        for (string::iterator i = x.begin(); i != x.end(); i++)
            putchar(*i);
    }
    inline bool getline(Octane_t &io, string s)
    {
        s = "";
        char ch = getchar();
        if (ch == EOF)
            return false;
        while (ch != '\n' and ch != EOF)
            s += ch, ch = getchar();
        return true;
    }
#endif

// support for initializer_list
#if __cplusplus >= 201103L
    template <typename T, typename... T1>
    inline int read(T &a, T1 &...other)
    {
        return read(a) + read(other...);
    }
    template <typename T, typename... T1>
    inline void print(T a, T1... other)
    {
        print(a);
        print(other...);
    }
#endif

    //  give up iostream
    template <typename T>
    Octane_t &operator>>(Octane_t &io, T &b)
    {
        return io.flag = read(b), io;
    }
    Octane_t &operator>>(Octane_t &io, char *b)
    {
        return io.flag = read(b), io;
    }
    template <typename T>
    Octane_t &operator<<(Octane_t &io, T b)
    {
        return print(b), io;
    }

#define cout io
#define cin io
#define endl '\n'
#undef ll
#undef db
#undef ldb
#undef BUFFER_SIZE
}
using namespace Octane;
struct node
{
    int l, r;
    mutable long long val;
    node(int L, int R = -1, long long Val = 0)
    {
        l = L, r = R, val = Val;
    }
    bool operator<(const node &a) const
    {
        return l < a.l;
    }
};
const int mod = 1e9 + 7;
typedef pair<long long, int> pii;
set<node> odt;
long long a[100005], n, m, seed, vmax;
long long fpow(long long x, long long y, long long mod = 1e9 + 7)
{
    long long ans = 1;
    x %= mod;
    while (y)
    {
        if (y & 1)
            ans = ans * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ans;
}
auto split(int pos)
{
    auto it = odt.lower_bound(node(pos));
    if (it != odt.end() && it->l == pos)
        return it;
    it--;
    int l = it->l, r = it->r;
    long long val = it->val;
    odt.erase(it);
    odt.insert(node(l, pos - 1, val));
    return odt.insert(node(pos, r, val)).first;
}
void assign(int l, int r, long long val)
{
    auto itr = split(r + 1), itl = split(l);
    odt.erase(itl, itr);
    odt.insert(node(l, r, val));
}
void add(int l, int r, long long val)
{
    auto itr = split(r + 1), itl = split(l);
    for (auto it = itl; it != itr; it++)
        it->val += val;
}
long long sum(int l, int r, int x)
{
    long long ans = 0;
    auto itr = split(r + 1), itl = split(l);
    for (auto it = itl; it != itr; it++)
        ans = (ans + fpow(it->val, x) * ((it->r) - (it->l) + 1)) % mod;
    return ans;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        odt.insert(node(i, i, a[i]));
    }
    for (int i = 1; i <= m; i++)
    {
        int op, l, r, x;
        cin >> op >> l >> r >> x;
        if (l > r)
            swap(l, r);
        if (op == 1)
            add(l, r, x);
        else if (op == 2)
            assign(l, r, x);
        else
            cout << sum(l, r, x) << endl;
    }
    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 2ms
memory: 1228kb

input:

458 823
14431 9895 11970 15308 2575 20181 709 27999 12992 18884 11061 16281 5044 28990 25092 28337 3...

output:

806084096
117884357
581509507
903754571
381316325
789203673
312340523
659242359
741787988
89040104
4...

result:

ok 261 lines

Test #2:

score: 10
Accepted
time: 0ms
memory: 1228kb

input:

481 526
8409 14498 18636 10027 24362 32458 17986 17730 11956 19192 2193 1034 29317 19284 16210 26242...

output:

867105097
717265913
288311190
320452351
133
498037408
473281413
216488030
182572597
611630662
471106...

result:

ok 179 lines

Test #3:

score: 10
Accepted
time: 124ms
memory: 8404kb

input:

100000 100000
15247 4194 9619 4532 22058 2667 21549 16652 25327 12018 13395 11426 7243 11714 22904 2...

output:

54433
544457741
352487648
82525935
532381851
235929450
38218
30045720
19138
459644406
33559
30953524...

result:

ok 33327 lines

Test #4:

score: 10
Accepted
time: 138ms
memory: 8400kb

input:

100000 100000
6264 26207 28424 24165 4852 20798 5803 18679 24588 12238 25786 28622 19900 101 25922 2...

output:

18923
13111195
41716
34447
32091
80654
731180277
9973
523560023
19797
159789457
695071461
3136
95363...

result:

ok 33328 lines

Test #5:

score: 10
Accepted
time: 144ms
memory: 8400kb

input:

100000 100000
15043 9299 7163 25384 24996 3803 24356 12466 22073 12987 8931 14997 3951 32704 23076 8...

output:

754347097
6296
588341566
325967942
180064833
683
831351544
63953
57030
17635
175222109
5280
57193
32...

result:

ok 33349 lines

Test #6:

score: 10
Accepted
time: 145ms
memory: 8400kb

input:

100000 100000
14736 16956 19864 23894 29403 5507 12182 6188 17192 14440 18618 3970 15396 15037 23334...

output:

17008
73008
935797904
16519312
15383
25232
236856418
75334
25854
46510
797344028
517157465
595936107...

result:

ok 33304 lines

Test #7:

score: 10
Accepted
time: 48ms
memory: 4892kb

input:

50000 50000
17799 29763 25337 21321 1391 31852 27418 28753 18524 14044 15976 18893 12274 22834 11348...

output:

19498
473297203
695948777
299749756
50630760
692747746
369627246
181903142
328502296
939823794
69850...

result:

ok 16802 lines

Test #8:

score: 10
Accepted
time: 69ms
memory: 4888kb

input:

50000 50000
10654 14956 14287 25326 8102 30579 11682 23553 272 22672 14460 30241 13026 12738 4912 72...

output:

717018991
140916081
273712387
602991268
878512570
665908548
10388
4939
283493752
435656498
657720400...

result:

ok 16814 lines

Test #9:

score: 10
Accepted
time: 129ms
memory: 7700kb

input:

90000 90000
29538 28214 24706 30393 27759 9002 13458 10243 15713 14881 10630 5593 7942 24578 29370 1...

output:

738835738
738703020
3888
402391875
37270
872563699
273399892
807398793
365897262
255303782
93280847
...

result:

ok 29904 lines

Test #10:

score: 10
Accepted
time: 150ms
memory: 8404kb

input:

100000 100000
23515 49 31372 25112 16779 21279 30735 32743 14678 15189 1763 23114 32215 14873 20487 ...

output:

576735050
562509678
553431297
662173102
515338212
478400370
879269281
500659410
483381164
1679282
16...

result:

ok 33309 lines