Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing7 minutes read (About 1120 words)

2013ACM-ICPC杭州赛区全国邀请赛

Transformation（HDU 4578）

Time Limit: 15000/8000 MS (Java/Others) Memory Limit: 65535/65536 K (Java/Others)

Problem Description

Yuanfang is puzzled with the question below:
There are n integers, a1, a2, …, an. The initial values of them are 0. There are four kinds of operations.
Operation 1: Add c to each number between ax and ay inclusive. In other words, do transformation ak<—ak+c, k = x,x+1,…,y.
Operation 2: Multiply c to each number between ax and ay inclusive. In other words, do transformation ak<—ak×c, k = x,x+1,…,y.
Operation 3: Change the numbers between ax and ay to c, inclusive. In other words, do transformation ak<—c, k = x,x+1,…,y.
Operation 4: Get the sum of p power among the numbers between ax and ay inclusive. In other words, get the result of axp+ax+1p+…+ay p.
Yuanfang has no idea of how to do it. So he wants to ask you to help him.

Input

There are no more than 10 test cases.
For each case, the first line contains two numbers n and m, meaning that there are n integers and m operations. 1 <= n, m <= 100,000.
Each the following m lines contains an operation. Operation 1 to 3 is in this format: “1 x y c” or “2 x y c” or “3 x y c”. Operation 4 is in this format: “4 x y p”. (1 <= x <= y <= n, 1 <= c <= 10,000, 1 <= p <= 3)
The input ends with 0 0.

Output

For each operation 4, output a single integer in one line representing the result. The answer may be quite large. You just need to calculate the remainder of the answer when divided by 10007.

Sample Input

5 5
3 3 5 7
1 2 4 4
4 1 5 2
2 2 5 8
4 3 5 3
0 0

Sample Output

307
7489

  • TLE，不必在每次query时都更新到叶结点 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    struct Node
    {
        int l,r,mid;
        LL v,add,mul;
    } SegTree[maxn*4];

    void build(int rt,int l,int r)
    {
        SegTree[rt].l=l;SegTree[rt].r=r;
        SegTree[rt].mid=(l+r)>>1;
        SegTree[rt].add=SegTree[rt].v=0;
        SegTree[rt].mul=1;
        if (l<r)
        {
            build(rt<<1,l,SegTree[rt].mid);
            build(rt<<1|1,SegTree[rt].mid+1,r);
        }
    }

    void add(int rt,int x,int y,int num)
    {
        int &l=SegTree[rt].l,&r=SegTree[rt].r,&mid=SegTree[rt].mid;
        if (x>y) return;
        //cout<<"+ "<<rt<<' '<<l<<' '<<r<<' '<<mid<<"  "<<x<<' '<<y<<' '<<num<<endl;
        if (x<=SegTree[rt].l&&SegTree[rt].r<=y)
        {
            SegTree[rt].add+=num;
            SegTree[rt].add%=mod;
            return;
        }
        int tmp=SegTree[rt].add;
        if (SegTree[rt].add)
        {

            SegTree[rt].add=0;
            add(rt,SegTree[rt].l,x-1,tmp);
            add(rt,y+1,SegTree[rt].r,tmp);
        }
        if (x<=mid) add(rt<<1,x,min(mid,y),tmp+num);
        if (y>mid) add(rt<<1|1,max(mid+1,x),y,tmp+num);
    }

    void mul(int rt,int x,int y,int num)
    {
        int &l=SegTree[rt].l,&r=SegTree[rt].r,&mid=SegTree[rt].mid;
        if (x>y) return;
        if (x<=SegTree[rt].l&&SegTree[rt].r<=y)
        {
            SegTree[rt].mul*=num;SegTree[rt].mul%=mod;
            SegTree[rt].add*=num;SegTree[rt].add%=mod;
            return;
        }
        int tmp=SegTree[rt].mul;
        if (SegTree[rt].mul!=1)
        {
            SegTree[rt].mul=1;
            add(rt,SegTree[rt].l,x-1,SegTree[rt].add*tmp);
            mul(rt,SegTree[rt].l,x-1,tmp);
            add(rt,x,y,SegTree[rt].add*tmp*num);
            add(rt,y+1,SegTree[rt].r,SegTree[rt].add*tmp);
            mul(rt,y+1,SegTree[rt].r,tmp);
        }
        if (x<=mid) mul(rt<<1,x,min(mid,y),tmp*num);
        if (y>mid) mul(rt<<1|1,max(mid+1,x),y,tmp*num);
    }

    void cover(int rt,int x,int y,int num)
    {
        int &l=SegTree[rt].l,&r=SegTree[rt].r,&mid=SegTree[rt].mid;
        if (x>y) return;
        //cout<<"c "<<rt<<' '<<l<<' '<<r<<' '<<mid<<"  "<<x<<' '<<y<<' '<<num<<endl;
        if (x<=SegTree[rt].l&&SegTree[rt].r<=y)
        {
            SegTree[rt].v=num;
            SegTree[rt].add=0;
            SegTree[rt].mul=1;
            return;
        }
        if (SegTree[rt].add)
        {
            int tmp=SegTree[rt].add;
            SegTree[rt].add=0;
            add(rt,SegTree[rt].l,x-1,tmp);
            add(rt,y+1,SegTree[rt].r,tmp);
        }
        if (SegTree[rt].mul!=1)
        {
            int tmp=SegTree[rt].mul;
            SegTree[rt].mul=1;
            mul(rt,SegTree[rt].l,x-1,tmp);
            mul(rt,y+1,SegTree[rt].r,tmp);
        }
        if (x<=mid) cover(rt<<1,x,min(mid,y),num);
        if (y>mid) cover(rt<<1|1,max(mid+1,x),y,num);
    }

    LL query(int rt,int x,int y,int p)
    {
        int &l=SegTree[rt].l,&r=SegTree[rt].r,&mid=SegTree[rt].mid;
        //cout<<"q "<<rt<<' '<<l<<' '<<r<<' '<<mid<<"  "<<SegTree[rt].v<<' '<<SegTree[rt].add<<' '<<SegTree[rt].mul<<endl; //<<"  "<<x<<' '<<y<<' '<<endl;
        if (SegTree[rt].l==SegTree[rt].r)
        //if (SegTree[rt].v)
        {
            SegTree[rt].v*=SegTree[rt].mul;SegTree[rt].v%=mod;
            SegTree[rt].v+=SegTree[rt].add;SegTree[rt].v%=mod;
            SegTree[rt].add=0;
            SegTree[rt].mul=1;
            switch(p)
            {
                case 1:return SegTree[rt].v;
                case 2:return SegTree[rt].v*SegTree[rt].v%mod;
                case 3:return SegTree[rt].v*SegTree[rt].v*SegTree[rt].v%mod;
            }

        }
        if (SegTree[rt].v)
        {
            add(rt<<1,l,mid,SegTree[rt].v*SegTree[rt].mul+SegTree[rt].add);
            add(rt<<1|1,mid+1,r,SegTree[rt].v*SegTree[rt].mul+SegTree[rt].add);
            SegTree[rt].v=0;
        }
        if (SegTree[rt].add)
        {
            //puts("update");
            add(rt<<1,l,mid,SegTree[rt].add);
            add(rt<<1|1,mid+1,r,SegTree[rt].add);
            SegTree[rt].add=0;
        }
        if (SegTree[rt].mul!=1)
        {
            mul(rt<<1,l,mid,SegTree[rt].mul);
            mul(rt<<1|1,mid+1,r,SegTree[rt].mul);
            SegTree[rt].mul=1;
        }
        return (((x<=mid)?query(rt<<1,x,min(mid,y),p):0)+((y>mid)?query(rt<<1|1,max(mid+1,x),y,p):0))%mod;

    }

    LL fnd(int rt,int x)
    {
        if(SegTree[rt].l==SegTree[rt].r) return SegTree[rt].v;
        else if (x<=SegTree[rt].mid) return fnd(rt<<1,x);
        else return fnd(rt<<1|1,x);
    }

    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            if (!n&&!m) break;
            build(1,1,n);
            for(int i=1;i<=m;i++)
            {
                int op,x,y,c;
                scanf("%d%d%d%d",&op,&x,&y,&c);
                switch(op)
                {
                    case 1:
                        add(1,x,y,c);//query(1,x,y,1);
                        break;
                    case 2:
                        mul(1,x,y,c);//query(1,x,y,1);
                        break;
                    case 3:
                        cover(1,x,y,c);//query(1,x,y,1);
                        break;
                    case 4:
                        printf("%I64d\n",query(1,x,y,c));
                        break;
                }
                //for(int i=1;i<=n;i++) printf("%lld ",fnd(1,i));printf("\n");
            }
        }
        return 0;
    }

  • AC 4882MS 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    #include<cctype>
    #include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<string>
    #include<queue>
    #include<stack>
    #include<set>
    #include<map>
    #define CLEAR(a) memset((a),0,sizeof((a)))

    using namespace std;

    typedef long long LL;
    const double pi = acos(-1.0);
    const int maxn = 1e5 + 10;
    const int inf = 99999999;
    const double eps = 1e-3;
    const int mod = 10007;

    struct Node
    {
        int l, r, mid;
        LL v, add, mul;
        bool up;
    } SegTree[maxn * 4];

    void build(int rt, int l, int r)
    {
        SegTree[rt].l = l;
        SegTree[rt].r = r;
        SegTree[rt].mid = (l + r) >> 1;
        SegTree[rt].add = SegTree[rt].v = 0;
        SegTree[rt].mul = 1;
        if (l < r)
        {
            SegTree[rt].up = 0;
            build(rt << 1, l, SegTree[rt].mid);
            build(rt << 1 | 1, SegTree[rt].mid + 1, r);
        }
        else
        {
            SegTree[rt].up = 1;
        }
    }

    void pushdown(int rt)
    {
        int mid = SegTree[rt].mid;
        if (SegTree[rt].up)
        {
            SegTree[rt << 1].add = SegTree[rt << 1 | 1].add = 0;
            SegTree[rt << 1].mul = SegTree[rt << 1 | 1].mul = 1;
            SegTree[rt << 1].v = SegTree[rt << 1 | 1].v = SegTree[rt].v;
            SegTree[rt << 1].up = SegTree[rt << 1 | 1].up = 1;
            SegTree[rt].up = 0;
        }
        else
        {
            if (SegTree[rt].add)
            {
                if (SegTree[rt << 1].up)
                {
                    SegTree[rt << 1].v += SegTree[rt].add;
                    SegTree[rt << 1].v %= mod;
                }
                else
                {
                    pushdown(rt << 1);
                    SegTree[rt << 1].add += SegTree[rt].add;
                    SegTree[rt << 1].add %= mod;
                }
                if (SegTree[rt << 1 | 1].up)
                {
                    SegTree[rt << 1 | 1].v += SegTree[rt].add;
                    SegTree[rt << 1 | 1].v %= mod;
                }
                else
                {
                    pushdown(rt << 1 | 1);
                    SegTree[rt << 1 | 1].add += SegTree[rt].add;
                    SegTree[rt << 1 | 1].add %= mod;
                }
                SegTree[rt].add = 0;
            }
            if (SegTree[rt].mul != 1)
            {
                if (SegTree[rt << 1].up)
                {
                    SegTree[rt << 1].v *= SegTree[rt].mul;
                    SegTree[rt << 1].v %= mod;
                }
                else
                {
                    pushdown(rt << 1);
                    SegTree[rt << 1].mul *= SegTree[rt].mul;
                    SegTree[rt << 1].mul %= mod;
                }
                if (SegTree[rt << 1 | 1].up)
                {
                    SegTree[rt << 1 | 1].v *= SegTree[rt].mul;
                    SegTree[rt << 1 | 1].v %= mod;
                }
                else
                {
                    pushdown(rt << 1 | 1);
                    SegTree[rt << 1 | 1].mul *= SegTree[rt].mul;
                    SegTree[rt << 1 | 1].mul %= mod;
                }
                SegTree[rt].mul = 1;
            }
        }
    }

    void update(int rt, int x, int y, LL num,int op)
    {
        int& l = SegTree[rt].l, &r = SegTree[rt].r, &mid = SegTree[rt].mid;
        //cout<<"+ "<<rt<<' '<<l<<' '<<r<<' '<<mid<<"  "<<x<<' '<<y<<' '<<num<<endl;
        if (x <= SegTree[rt].l && SegTree[rt].r <= y)
        {
            if (op==3)
            {
                SegTree[rt].add=0;
                SegTree[rt].mul=1;
                SegTree[rt].v=num;
                SegTree[rt].up=1;
            }
            else
            {
                if (SegTree[rt].up)
                {
                    if (op==1)
                    {
                        SegTree[rt].v+=num;SegTree[rt].v%=mod;
                    }
                    else
                    {
                        SegTree[rt].v*=num;SegTree[rt].v%=mod;
                    }
                }
                else
                {
                    pushdown(rt);
                    if (op==1)
                    {
                        SegTree[rt].add+=num;SegTree[rt].add%=mod;
                    }
                    else
                    {
                        SegTree[rt].mul*=num;SegTree[rt].mul%=mod;
                    }
                }
            }
            return;
        }
        pushdown(rt);
        if (x <= mid)
            update(rt << 1, x, min(mid, y), num,op);
        if (y > mid)
            update(rt << 1 | 1, max(mid + 1, x), y, num,op);
    }

    LL query(int rt, int x, int y, int p)
    {
        int& l = SegTree[rt].l, &r = SegTree[rt].r, &mid = SegTree[rt].mid;
        //cout<<"q "<<rt<<' '<<l<<' '<<r<<' '<<mid<<"  "<<SegTree[rt].v<<' '<<SegTree[rt].add<<' '<<SegTree[rt].mul<<endl; //<<"  "<<x<<' '<<y<<' '<<endl;
        if (x <= SegTree[rt].l && SegTree[rt].r <= y&&SegTree[rt].up)
        {
            LL tmp=LL(r-l+1)%mod;
            for(int i=1;i<=p;i++)
            {
                tmp*=SegTree[rt].v;tmp%=mod;
            }
            return tmp;
        }
        pushdown(rt);
        return (((x <= mid) ? query(rt << 1, x, min(mid, y), p) : 0LL) + ((y > mid) ? query(rt << 1 | 1, max(mid + 1, x), y, p) : 0LL)) % mod;
    }

    LL fnd(int rt, int x)
    {
        if (SegTree[rt].l == SegTree[rt].r)
        {
            return SegTree[rt].v;
        }
        else if (x <= SegTree[rt].mid)
        {
            return fnd(rt << 1, x);
        }
        else
        {
            return fnd(rt << 1 | 1, x);
        }
    }

    int main()
    {
        int n, m;
        while (~scanf("%d%d", &n, &m))
        {
            if (!n && !m)
            {
                break;
            }
            build(1, 1, n);
            for (int i = 1; i <= m; i++)
            {
                int op, x, y;
                LL c;
                scanf("%d%d%d%I64d", &op, &x, &y, &c);
                switch (op)
                {
                    case 1:
                    case 2:
                    case 3:
                        update(1, x, y, c,op); //query(1,x,y,1);
                        break;
                    case 4:
                        printf("%I64d\n", query(1, x, y, c));
                        break;
                }
                //for(int i=1;i<=n;i++) printf("%lld ",fnd(1,i));printf("\n");
            }
        }
        return 0;
    }

2013ACM-ICPC杭州赛区全国邀请赛

https://devblog.citruxonve.net/posts/4f35b530/

Author

Semprathlon / Simfae Dean

Posted on

05/09/2015

Updated on

07/19/2023

Licensed under

Comments

Follow

Categories

Tags

ACM-ICPC14
AC自动机1
AWS2
Adobe1
Angular1
Apache1
Arch Linux2
BFS2
BIT3
Bestcoder23
Bitset3
Bootstrap1
C++2
CCPC1
Catalan1
CentOS3
Clover2
Compiler1
Contest6
Cpp1
DFS3
DNS1
DP13
DSDT3
Data Analytics2
Dinic1
Docker1
Eclipse1
Expect1
Fibonacci1
Frontend1
GLUT1
GPT1
GUI1
Gentoo1
Geometry1
Git1
Github2
Graduate1
HTML1
Hash2
Heap1
Interview1
JNUOJ1
Java12
K8s1
KMP1
Linux3
Live Archive2
MBR1
MS=DOS1
Mac14
Manhattan1
Multi-Uni5
MySQL8
Möbius反演1
NAS2
NetworkFlow1
NoSQL1
OS2
OpenCV1
OpenGL2
Python10
RMQ1
Regional3
Repost1
Ryzen1
SQLserver1
SSL1
System Design1
TOEFL1
Template3
Tree1
Trie2
UEFI4
UX1
Ubuntu14
Unix1
Windows2
Wordpress3
ZFS1
ZOJ1
ajax1
asm1
css1
cuda1
cudnn1
curl1
docker1
es61
font1
ftp1
git1
gitlab1
hardware1
hdu2
hexo1
html1
https1
iOS1
interview1
java1
javascript1
jdk1
jquery1
js7
json1
kext1
macOS2
network1
nginx4
node1
nodejs1
npm1
php8
python1
react2
react native1
regex1
string4
二分图1
二分查找3
博弈1
容斥原理3
并查集1
并行计算1
微积分1
扫描线3
数列1
数独1
数论1
概率2
模拟4
欧拉回路1
百度之星1
知乎1
离散化1
约瑟夫1
线段树3
组合数学1
网络赛2
背包1
背包问题1
转载博文1
递归1

Subscribe for updates

Links

×