seven DAY

叕被虐了;

F.线段树

呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃

巨长,好吧,拉胯的数据结构;

但是,好用,他可以解决单点修改,单点询问,区间修改,区间询问各种问题;

在通过升级就

可以解决区间第K大或小的问题(主席树,权值线段树..)

由于码量太大就打了四道(在http://172.17.55.238/,3000还有一些13道)

就讲讲用线段树做区间乘法吧

首先,要先搞清楚运算顺序的问题;

我们选择先算乘法再算加法的

(即化成*a+b的样子,若再来一次就(*a’+b’)*a+b,以此类推,对对对)

然后,处理最重要的lazytage的问题


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
#include<bits/stdc++.h>
#define ll long long

#define zuo pos*2

#define you pos*2+1

using namespace std;
struct six{
    ll l;
    ll r;
    ll sum;
    ll mul;
    ll plue;
}tree[500010];
ll n,P,m,a[100010],i,t,g,c,k,len;
void push_down(ll pos,ll L,ll R)
{
    ll mid=(L+R)>>1;
    tree[zuo].sum*=tree[pos].mul;
    tree[zuo].sum%=P;
    tree[zuo].sum+=tree[pos].plue*(tree[zuo].r-tree[zuo].l+1)%P;
    tree[zuo].sum%=P;
    tree[you].sum*=tree[pos].mul;
    tree[you].sum%=P;
    tree[you].sum+=tree[pos].plue*(tree[you].r-tree[you].l+1)%P;
    tree[you].sum%=P;
    tree[zuo].mul*=tree[pos].mul;
    tree[zuo].mul%=P;
    tree[you].mul*=tree[pos].mul;
    tree[you].mul%=P;
    tree[zuo].plue*=tree[pos].mul;
    tree[zuo].plue%=P;
    tree[zuo].plue+=tree[pos].plue;
    tree[zuo].plue%=P;
    tree[you].plue*=tree[pos].mul;
    tree[you].plue%=P;
    tree[you].plue+=tree[pos].plue;
    tree[you].plue%=P;
    tree[pos].mul=1;
    tree[pos].plue=0;
    return ;
}//传递lazytage,plue为加法,mul为乘法;
void build(ll pos,ll L,ll R)
{
    tree[pos].l=L;
    tree[pos].r=R;
    tree[pos].mul=1;
    if(L==R)
    {
        tree[pos].sum=a[L];
        len=pos;
        return ;
    }
    ll mid=(L+R)>>1;
    build(zuo,L,mid);
    build(you,mid+1,R);
    tree[pos].sum=tree[zuo].sum+tree[you].sum;
    tree[pos].sum%=P;
    return ;
}// 建树,就不多讲了
void change1(ll pos,ll L,ll R,ll x,ll y,ll z)
{
    if(y<L||x>R)
    {
        return ;
    }
    if(x<=L&&R<=y)
    {
        tree[pos].sum*=z;
        tree[pos].sum%=P;
        tree[pos].mul*=z;
        tree[pos].mul%=P;
        tree[pos].plue*=z;
        tree[pos].plue%=P;
        return ;
    }
    ll mid=(L+R)>>1;
    push_down(pos,L,R);
    change1(zuo,L,mid,x,y,z);
    change1(you,mid+1,R,x,y,z);
    tree[pos].sum=tree[zuo].sum+tree[you].sum;
    tree[pos].sum%=P;
    return ;
}// 做乘法,一定要先乘后加!
void change2(ll pos,ll L,ll R,ll x,ll y,ll z)
{
    if(y<L||x>R)
    {
        return ;
    }
    if(x<=L&&R<=y)
    {
        tree[pos].sum+=z*(tree[pos].r-tree[pos].l+1);
        tree[pos].sum%=P;
        tree[pos].plue+=z;
        tree[pos].plue%=P;
        return ;
    }
    ll mid=(L+R)>>1;
    push_down(pos,L,R);
    change2(zuo,L,mid,x,y,z);
    change2(you,mid+1,R,x,y,z);
    tree[pos].sum=tree[zuo].sum+tree[you].sum;
    tree[pos].sum%=P;
    return ;
}//做加法
ll query(ll pos,ll L,ll R,ll x,ll y)
{
    if(y<L||x>R)
    {
        return 0;
    }
    if(x<=L&&R<=y)
    {
        return tree[pos].sum;
    }
    ll mid=(L+R)>>1,ans=0,s1=0,s2=0;
    push_down(pos,L,R);
    s1=query(zuo,L,mid,x,y)%P;
    s2=query(you,mid+1,R,x,y)%P;
    ans=s1+s2;
    return ans%P;
}// 询问
int main()
{
    cin>>n>>P;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(1,1,n);
    cin>>m;
    while(m--)
    {
        cin>>k;
        if(k==1)
        {
            cin>>t>>g>>c;
            change1(1,1,n,t,g,c);
        }
        if(k==2)
        {
            cin>>t>>g>>c;
            change2(1,1,n,t,g,c);
        }
        if(k==3)
        {
            cin>>t>>g;
            cout<<query(1,1,n,t,g)<<endl;
        }
    }
    return 0;
}

过程其实并不难,但要注意很多细节,错了还不好调试,所以打的时候要小心一点!

S.倍增(tarjan,倍增才是yyds)

倍增,从字面意思来理解就是成倍的增加,这也是它的本质思想,通过这种方法来缩减所损耗的时间,非常棒;

举个例子,栗子

这题是利用倍增求LCA的经典例题

思路简单,先求出(x,y)的LCA

如图,求7到5的最短距离

我们可以发现最短距离一定是他们到LCA的距离之和

so 先求LCA

计算出他们与LCA的距离;

相加,就OK了

也是一样细节很多

要注意一下不然就会

发表评论

邮箱地址不会被公开。 必填项已用*标注