线段树题单
admin
|
|
563
|
算法知识总结

2507 字
|
56 分钟

P3372 【模板】线段树 1 区间修改 区间查询 求和

P3373 【模板】线段树 2 区间修改(+, *) 区间查询 求和

HDU 1166 敌兵布阵 单点修改 区间查询 求和
HDU 1754 I Hate It 单点修改 区间查询 求max
POJ 3468 A Simple Problem with Integers区间修改 区间查询 求和
Just a Hook区间修改 区间查询 修改为特定值

Tunnel Warfare 单点修改，单点查询，最长的连续的1的长度

P4588 [TJOI2018]数学计算 单点修改，根结点查询，以时间为轴

P2574 XOR的艺术 区间修改(取反) 区间查询(求和)

P2846 [USACO08NOV]Light Switching G 区间修改(取反) 区间查询

 

P3372 【模板】线段树 1

题目描述：

区间修改 区间查询

如题，已知一个数列，你需要进行下面两种操作：

  1. 将某区间每一个数加上 kk。
  2. 求出某区间每一个数的和。

思路：

最模版的线段树，没什么好说的

写几个函数：

  • 建树
  • 标记下传
  • 区间修改
  • 区间查询

板子：

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<complex>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 1000000 + 50
#define seed 13331
#define mod1 1000000007
#define mod2 1000000009
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!提交不看数据范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

ll n, m, l, r, c, x;
ll tr[MAX], sum[MAX], add[MAX];

inline void built(ll p, ll l, ll r){//建树
    add[p] = 0;
    if(l == r){
        sum[p] = tr[l];//这里别写成l
        return;
    }
    ll mid = (l + r) / 2;
    built(p * 2, l, mid);
    built(p * 2 + 1, mid + 1, r);
    sum[p] = sum[p * 2] + sum[p * 2 + 1];
}

inline void pushdown(ll p, ll l, ll r){//懒惰标记下传
    ll mid = (l + r) / 2;
    sum[p * 2] += (mid - l + 1) * add[p];
    sum[p * 2 + 1] += (r - mid) * add[p];
    add[p * 2] += add[p];
    add[p * 2 + 1] += add[p];
    add[p] = 0;
}

inline void ad(ll p, ll l, ll r, ll s, ll t, ll c){
    if(l >= s && t >= r){
        add[p] += c;
        sum[p] += (r - l + 1) * c;
        return;
    }
    pushdown(p, l, r);
    ll mid = (l + r) / 2;
    if(mid >= s)ad(p * 2, l, mid, s, t, c);
    if(mid < t)ad(p * 2 + 1, mid + 1, r, s, t, c);
    sum[p] = sum[p * 2] + sum[p * 2 + 1];
}

inline ll getans(ll p, ll l, ll r, ll s, ll t){
    if(l >= s && t >= r){
        return sum[p];
    }
    pushdown(p, l, r);
    ll mid = (l + r) / 2;
    ll ans = 0;
    if(mid >= s)ans += getans(p * 2, l, mid, s, t);
    if(mid < t)ans += getans(p * 2 + 1, mid + 1, r, s, t);
    return ans;
}

int main(){
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= n; ++i)scanf("%lld", &tr[i]);
    built(1, 1, n);
    for(int i = 1; i <= m; ++i){
        scanf("%lld", &x);
        if(x == 1){
            scanf("%lld%lld%lld", &l, &r, &c);
            ad(1, 1, n, l, r, c);
        }
        else{
            scanf("%lld%lld", &l, &r);
            cout<<getans(1, 1, n, l, r)<<endl;
        }
    }
    return 0;
}

P3373 【模板】线段树 2

题目描述：

已知一个数列，你需要进行下面三种操作：

  • 将某区间每一个数乘上 x
  • 将某区间每一个数加上 x
  • 求出某区间每一个数的和

思路：

也算是一个板子题，不过懒惰标记得用俩，而且乘法与加法有先后顺序，写起来就会有亿点点混乱

细节下次再补

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<complex>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 1000000 + 50
#define seed 13331
#define mod1 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!提交不看数据范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

ll n, m, mod, l ,r, c, x;
ll tr[MAX], add[MAX], mu[MAX];
ll sum[MAX];

inline void built(ll p, ll l, ll r){
    add[p] = 0;mu[p] = 1;
    if(l == r){
        sum[p] = tr[l] % mod;
        return;
    }
    ll mid = (l + r) / 2;
    built(p * 2, l, mid);
    built(p * 2 + 1, mid + 1, r);
    sum[p] = (sum[p * 2] + sum[p * 2 + 1]) % mod;
}

inline void pushdowm(ll p, ll l, ll r){
    ll mid = (l + r) / 2;
    sum[p * 2] = ((sum[p * 2] * mu[p]) % mod + (add[p] * (mid - l + 1)) % mod) % mod;
    sum[p * 2 + 1] = ((sum[p * 2 + 1] * mu[p]) % mod + (add[p] * (r - mid)) % mod) % mod;
    mu[p * 2] = mu[p * 2] * mu[p] % mod;
    mu[p * 2 + 1] = mu[p * 2 + 1] * mu[p] % mod;
    add[p * 2] = (add[p] + add[p * 2] * mu[p]) % mod;
    add[p * 2 + 1] = (add[p * 2 + 1] * mu[p] + add[p]) % mod;
    add[p] = 0;mu[p] = 1;
}

inline void ad(ll p, ll l, ll r, ll s, ll t, ll c){
    if(l >= s && t >= r){
        add[p] = (add[p] + c) % mod;
        sum[p] = (sum[p] + (r - l + 1) * c) % mod;
        return;
    }
    pushdowm(p, l, r);
    ll mid = (l + r) / 2;
    if(mid >= s)ad(p * 2, l, mid, s, t, c);
    if(mid < t)ad(p * 2 + 1, mid + 1, r, s, t, c);
    sum[p] = (sum[p * 2] + sum[p * 2 + 1]) % mod;
}

inline void mul(ll p, ll l, ll r, ll s, ll t, ll c){
    if(l >= s && t >= r){
        add[p] = (add[p] * c) % mod;
        mu[p] = (mu[p] * c) % mod;
        sum[p] = (sum[p] * c) % mod;
        return;
    }
    pushdowm(p, l, r);
    ll mid = (l + r) / 2;
    if(mid >= s)mul(p * 2, l, mid, s, t, c);
    if(mid < t)mul(p * 2 + 1, mid + 1, r, s, t, c);
    sum[p] = (sum[p * 2] + sum[p * 2 + 1]) % mod;
}

inline ll getans(ll p, ll l, ll r, ll s, ll t){
    if(l >= s && t >= r){
        return sum[p] % mod;
    }
    pushdowm(p, l, r);
    ll ans = 0;
    ll mid = (l + r) / 2;
    if(mid >= s)ans += getans(p * 2, l, mid, s, t);
    if(mid < t)ans += getans(p * 2 + 1, mid + 1, r, s, t);
    return ans % mod;
}

int main(){
    scanf("%lld%lld%lld",&n, &m, &mod);
    for(int i = 1; i <= n; ++i)scanf("%lld", &tr[i]);
    built(1, 1, n);
    for(int i = 1; i <= m; ++i){
        scanf("%lld", &x);
        if(x == 1){
            scanf("%lld%lld%lld", &l, &r, &c);
            mul(1, 1, n, l, r, c);
        }
        else if(x == 2){
            scanf("%lld%lld%lld", &l, &r, &c);
            ad(1, 1, n, l, r, c);
        }
        else if(x == 3){
            scanf("%lld%lld", &l, &r);
            printf("%lld\n", getans(1, 1, n, l, r));
        }
    }
    return 0;
}

敌兵布阵

题目描述：

单点修改 区间查询

四种操作

  • Add i, j 给第 i 个数加上 j
  • Sub i, j 给第 i 个数减去 j
  • Query i, j 询问区间 [i, j] 的和
  • End 结束
//线段树：（560ms
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 50000 + 50
#define mod 998244353
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
//不开longlong见祖宗!提交不看数据范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m, l, r, t;
char x;
string s;
int sum[4 * MAX];
int tr[MAX];

inline void pushup(int p){
    sum[p] = sum[p * 2] + sum[p * 2 + 1];
}

inline void built(int p, int l, int r){
    if(l == r){
        sum[p] = tr[l];
        return;
    }
    int mid = (l + r) / 2;
    built(p * 2, l, mid);
    built(p * 2 + 1, mid + 1, r);
    pushup(p);
}

inline void update(int p, int l, int r, int pos, int c){
    if(l == r){
        sum[p] += c;
        return;
    }
    int mid = (l + r) / 2;
    if(mid >= pos)update(p * 2, l, mid, pos, c);
    else update(p * 2 + 1, mid + 1, r, pos, c);
    pushup(p);
}

inline int getans(int p, int l, int r, int s, int t){
    if(l >= s && t >= r){
        return sum[p];
    }
    int mid = (l + r) / 2;
    int ans = 0;
    if(mid >= s)ans += getans(p * 2, l, mid, s, t);
    if(mid < t)ans +=  getans(p * 2 + 1, mid + 1, r, s, t);
    return ans;
}

int main(){
    scanf("%d", &t);
    for(int p = 1; p <= t; ++p) {
        cout<<"Case "<<p<<":\n";
        scanf("%d", &n);
        for(int i = 1;  i<= n; ++i)scanf("%d", &tr[i]);
        built(1, 1, n);
        while (cin>>s && s[0] != 'E') {
            scanf("%d%d", &l, &r);
            if(s[0] == 'A'){
                update(1, 1, n, l, r);
            }
            else if(s[0] == 'S'){
                update(1, 1, n, l, -r);
            }
            else if(s[0] == 'Q'){
                cout<<getans(1, 1, n, l, r)<<endl;
            }
        }
        }
    return 0;
}

I Hate It

题目描述：

单点修改

区间查询max

//线段树板子
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 200000 + 50
#define mod 998244353
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
//不开longlong见祖宗!提交不看数据范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m, l, r;
char x;
int ma[4 * MAX];
int tr[MAX];

inline void pushup(int p){
    ma[p] = max(ma[p * 2], ma[p * 2 + 1]);
}

inline void built(int p, int l, int r){
    if(l == r){
        ma[p] = tr[l];
        return;
    }
    int mid = (l + r) / 2;
    built(p * 2, l, mid);
    built(p * 2 + 1, mid + 1, r);
    pushup(p);
}

inline void update(int p, int l, int r, int pos, int c){
    if(l == r){
        ma[p] = c;
        return;
    }
    int mid = (l + r) / 2;
    if(mid >= pos)update(p * 2, l, mid, pos, c);
    else update(p * 2 + 1, mid + 1, r, pos, c);
    pushup(p);
}

inline int getans(int p, int l, int r, int s, int t){
    if(l >= s && t >= r){
        return ma[p];
    }
    int mid = (l + r) / 2;
    int ans = -inf;
    if(mid >= s)ans = max(ans, getans(p * 2, l, mid, s, t));
    if(mid < t)ans = max(ans, getans(p * 2 + 1, mid + 1, r, s, t));
    return ans;
}

int main(){
    while (scanf("%d%d", &n, &m) != EOF) {
        for(int i = 1;  i<= n; ++i)scanf("%d", &tr[i]);
        built(1, 1, n);
        for(int i = 1; i <= m; ++i){
            scanf(" %c%d%d",&x, &l, &r);
            if(x == 'Q'){
                int ans = getans(1, 1, n, l, r);
                printf("%d\n", ans);
            }
            else{
                update(1, 1, n, l, r);
            }
        }
    }
    
    return 0;
}

A Simple Problem with Integers

题目描述：

区间修改

区间查询

// 线段树 2844ms
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 100000 + 50
#define MOD 1000000007
#define mod(x) ((x)%MOD)
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%lld",&n)
#define sdd(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%lld\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!提交不看数据范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

ll n, m, x, y, c;
char op;
ll sum[4 * MAX];
ll ad[4 * MAX];
ll tr[MAX];

inline void pushup(ll p){
    sum[p] = sum[p * 2] + sum[p * 2 + 1];
}

inline void pushdown(ll p, ll l, ll r){
    ll mid = (l + r) / 2;
    sum[p * 2] += ad[p] * (mid - l + 1);
    sum[p * 2 + 1] += ad[p] * (r - mid);
    ad[p * 2] += ad[p];
    ad[p * 2 + 1] += ad[p];
    ad[p] = 0;
}

inline void built(ll p, ll l, ll r){
    ad[p] = 0;
    if(l == r){
        sum[p] = tr[l];
        return;
    }
    ll mid = (l + r) / 2;
    built(p * 2, l, mid);
    built(p * 2 + 1, mid + 1, r);
    pushup(p);
}

inline ll getans(ll p, ll l, ll r, ll s, ll t){
    if(l >= s && t >= r){
        return sum[p];
    }
    pushdown(p, l, r);
    ll mid = (l + r) / 2;
    ll ans = 0;
    if(mid >= s)ans += getans(p * 2, l, mid, s, t);
    if(mid < t)ans += getans(p * 2 + 1, mid + 1, r, s, t);
    return ans;
}

inline void updata(ll p, ll l, ll r, ll s, ll t, ll c){
    if(l >= s && t >= r){
        sum[p] += (r - l  + 1) * c;
        ad[p] += c;
        return;
    }
    ll mid = (l + r) / 2;
    pushdown(p, l, r);
    if(mid >= s)updata(p * 2, l, mid, s, t, c);
    if(mid < t)updata(p * 2 + 1, mid + 1, r, s, t, c);
    pushup(p);
}


int main(){
    sdd(n, m);
    for(int i = 1; i <= n; ++i)sd(tr[i]);
    built(1, 1, n);
    while (m--) {
        cin>>op;
        if(op == 'Q'){
            sdd(x, y);
            cout<<getans(1, 1, n, x, y)<<endl;;
        }
        else {
            sddd(x, y, c);
            updata(1, 1, n, x, y, c);
        }
    }
    return 0;
}

Just a Hook

题目描述：

区间修改 区间查询 修改成特定值

思路

线段树

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 100000 + 50
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!提交不看数据范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m, t;
int x, y, c;
int sum[4 * MAX];
int ta[4 * MAX];
int tr[MAX];

inline void pushup(int p){
    sum[p] = sum[p * 2] + sum[p * 2 + 1];
}

inline void pushdown(int p, int l, int r){
    if(ta[p]){
        int mid = (l + r) / 2;
        sum[p * 2] = ta[p] * (mid - l + 1);
        sum[p * 2 + 1] = ta[p] * (r - mid);
        ta[p * 2] = ta[p * 2 + 1] = ta[p];
        ta[p] = 0;
    }
}

inline void built(int p, int l, int r){
    ta[p] = 0;
    if(l == r){
        sum[p] = 1;
        return;
    }
    int mid = (l + r) / 2;
    built(p * 2, l, mid);
    built(p * 2 + 1, mid + 1, r);
    pushup(p);
}

inline void update(int p, int l, int r, int s, int t, int c){
    if(l >= s && t >= r){
        sum[p] =  (r - l + 1) * c;
        ta[p] = c;
        return;
    }
    pushdown(p, l, r);
    int mid = (l + r) / 2;
    if(mid >= s)update(p * 2, l, mid, s, t, c);
    if(mid < t)update(p * 2 + 1, mid + 1, r, s, t, c);
    pushup(p);
}



int main(){
    sd(t);
    for(int p = 1; p <= t; ++p) {
        mem(ta, 0);
        sdd(n, m);
        built(1, 1, n);
        while (m--) {
            sddd(x, y, c);
            update(1, 1, n, x, y, c);
        }
        printf("Case %d: The total value of the hook is %d.\n",p,sum[1]);
    }
    return 0;
}

Tunnel Warfare

题目描述：

初始是一段全是1的串

有三种操作

  • 'D x'，将x位置的1变成0
  • 'R' 将上一个变成0的点变回1
  • 'Q x' 询问第x的位置与左右相连续的1的数量是多少

思路

线段树

单点修改，单点查询

维护三个变量

一个是维护当前区间连续1的数量的最大值

一个是维护当前区间从最左开始的最长连续1的数量

最后一个是维护当前区间从最右开始的最长连续1的数量

具体细节以后再补

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 200000 + 50
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!提交不看数据范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m, x;
int mle[MAX], rle[MAX], lle[MAX];
char op;
stack<int>st;

inline void built(int p, int l, int r){
    mle[p] = rle[p] = lle[p] = r - l + 1;
    if(l == r)return;
    int mid = (l + r) / 2;
    built(p * 2, l, mid);
    built(p * 2 + 1, mid + 1, r);
}

inline void update(int p, int l, int r, int x, int c){
    if(x < l || x > r)return;
    if(l == r){
        mle[p] = rle[p] =  lle[p] = c;
        return;
    }
    int mid = (l + r) / 2;
    update(p * 2, l, mid, x, c);
    update(p * 2 + 1, mid + 1, r, x, c);
    
    mle[p] = max(max(mle[p * 2], mle[p * 2 + 1]), rle[p * 2] + lle[p * 2 + 1]);
    lle[p] = lle[p * 2];
    if(lle[p] == mid - l + 1)lle[p] += lle[p * 2 + 1];
    rle[p] = rle[p * 2 + 1];
    if(rle[p] == r - mid)rle[p] += rle[p * 2];
}

inline int getans(int p, int l, int r, int x){
    if(l == r || mle[p] == r - l + 1 || !mle[p])return mle[p];
    int mid = (l + r) / 2;
    if(x <= mid - rle[p * 2])return getans(p * 2, l, mid, x);
    if(x > mid + lle[p * 2 + 1])return getans(p * 2 + 1, mid + 1, r, x);
    return rle[p * 2] + lle[p * 2 + 1];
}

int main(){
    while(sdd(n, m) != EOF){
        built(1, 1, n);
        for(int i = 1; i <= m; ++i){
            cin>>op;
            if(op == 'D'){
                sd(x);
                update(1, 1, n, x, 0);
                st.push(x);
            }
            else if(op == 'R'){
                x = st.top();
                update(1, 1, n, x, 1);
                st.pop();
            }
            else {
                sd(x);
                cout<<getans(1, 1, n, x)<<endl;
            }
        }
    }
    
    return 0;
}

P4588 [TJOI2018]数学计算

题目描述：

小豆现在有一个数 xx，初始值为 11。小豆有 QQ 次操作，操作有两种类型：

1 m：将 x变为 x × m，并输出 x modM

2 pos：将 x变为 x 除以第 pos次操作所乘的数（保证第 pos 次操作一定为类型 1，对于每一个类型 1 的操作至多会被除一次），并输出 x mod M。

思路

线段树，不过确实没看出来是线段树

一开始看寻思直接模拟吧，但是发现得求好多好多个逆元，没法搞

如何解决？

以时间为轴，建立线段树，叶子结点维护该操作时间的乘数，非叶子结点维护区间乘，叶子结点开始都为0

然后每次乘就进行单点修改，修改成c，输出mul[1] % mod

每次除也是进行单点修改，修改成1，输出mul[1] % mod

写的时候有一个地方卡了半个小时，就是刚开始用p代表的mod，而建树和单点更新的函数里面也有p，就冲突了，直到重写才发现

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 100000 + 50
//#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%lld",&n)
#define sdd(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!提交不看数据范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int t, n, c, op;
ll mod;
ll p;
ll mul[4 * MAX];

inline void pushup(int p){
    mul[p] = (mul[p * 2] * mul[p * 2 + 1]) % mod;
}

inline void built(int p, int l, int r){
    mul[p] = 1;
    if(l == r)return;
    int mid = (l + r) / 2;
    built(p * 2, l, mid);
    built(p * 2 + 1, mid + 1, r);
    pushup(p);
}

void update(int p, int l, int r, int x, int c){
    if(l == r){
        mul[p] = c;
        return;
    }
    int mid = (l + r) / 2;
    if(mid >= x)update(p * 2, l, mid, x, c);
    else update(p * 2 + 1, mid + 1, r, x, c);
    pushup(p);
}


int main(){
    io;
    cin>>t;
    while (t--) {
        cin>>n>>mod;
        built(1, 1, n);
//        cout<<mul[1]<<endl;
        for(int i = 1; i <= n; ++i){
            cin>>op>>c;
            if(op == 1){
                update(1, 1, n, i, c);
                cout<<mul[1]<<endl;
            }
            else {
                update(1, 1, n, c, 1);
                cout<<mul[1]<<endl;
            }
        }
    }
    return 0;
}

P2574 XOR的艺术

题目描述：

有一个01串，两种操作

  • '0 l r'将[l, r]中1变0，0变1
  • '1 l r '求[l, r]中1的个数

思路

区间修改 区间查询，就拿线段树搞搞

这里涉及到了取反，就可以利用 ^1 来实现

而一个数取反两次相当于不变，也就是异或1两次就不变

所以我们可以用sum数组维护区间和，用tag数组作为懒惰标记，

tag只有两个值，0或1，0代表当前区间不用取反，1代表当前区间需要取反

主要是懒惰标记下传的函数不好写：

取反，所有的0变成1，所有的1变成0，sum代表区间的1的数量，故一次取反就使得sum[p] = r – l + 1 – sum[p]，即区间长度减去原来1的数量

所以左子树和右子树的tag都^1,sum就等于各自长度-各自sum

建树，求和和之前一样，直接套就可以

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 200000 + 50
//#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%lld",&n)
#define sdd(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!提交不看数据范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m, l, r, op;
string s;
int tr[MAX];
int ta[4 * MAX];
int sum[4 * MAX];

inline void pushup(int p){
    sum[p] = sum[p * 2] + sum[p * 2 + 1];
}

inline void pushdown(int p, int l, int r){
    int mid = (l + r) / 2;
    if(ta[p]){
        sum[p * 2] = mid - l + 1 - sum[p * 2];
        sum[p * 2 + 1] = r - mid - sum[p * 2 + 1];
        ta[p * 2] ^= 1;
        ta[p * 2 + 1] ^= 1;
        ta[p] = 0;
    }
}

inline void built(int p, int l, int r){
    ta[p] = 0;
    if(l == r){
        sum[p] = tr[l];
        return;
    }
    int mid = (l + r) / 2;
    built(p * 2, l, mid);
    built(p * 2 + 1, mid + 1, r);
    pushup(p);
}

inline void update(int p, int l, int r, int s, int t){
    if(l >= s && t >= r){
        ta[p] ^= 1;
        sum[p] = (r - l + 1) - sum[p];
        return;
    }
    pushdown(p, l, r);
    int mid = (l + r) / 2;
    if(mid >= s)update(p * 2, l, mid, s, t);
    if(mid < t)update(p * 2 + 1, mid + 1, r, s, t);
    pushup(p);
}

inline int getans(int p, int l, int r, int s, int t){
    if(l >= s && t >= r){
        return sum[p];
    }
    pushdown(p, l, r);
    int mid = (l + r) / 2;
    int ans = 0;
    if(mid >= s)ans += getans(p * 2, l, mid, s, t);
    if(mid < t)ans += getans(p * 2 + 1, mid + 1, r, s, t);
    return ans;
}

int main(){
    io;
    cin>>n>>m;
    cin>>s;
    for(int i = 0; i < s.size(); ++i)tr[i + 1] = s[i] - '0';
    built(1, 1, n);
    for(int i = 1; i <= m; ++i){
        cin>>op>>l>>r;
        if(!op){
            update(1, 1, n, l, r);
        }
        else{
            cout<<getans(1, 1, n, l, r)<<endl;
        }
    }
    return 0;
}

P2846 [USACO08NOV]Light Switching G

题目描述：

n个灯，两种操作

  • 0 x y 将x到y的灯 亮的变成暗的，暗的变成亮的
  • 1 x y 问x到y中亮着的灯的数量

思路：

同样是区间取反，区间查询

和上面那个题一样（经验加倍耶✌️

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 100000 + 50
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!提交不看数据范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m ,x, y, c, op;
int tr[MAX];
int ta[4 * MAX];
int sum[4 * MAX];

inline void pushup(int p){
    sum[p] = sum[p * 2] + sum[p * 2 + 1];
}

inline void pushdown(int p, int l, int r){
    if(ta[p]){
        int mid = (l + r) / 2;
        sum[p * 2] = (mid - l + 1) - sum[p * 2];
        sum[p * 2 + 1] = (r - mid) - sum[p * 2 + 1];
        ta[p * 2] ^= 1;
        ta[p * 2 + 1] ^= 1;
        ta[p] = 0;
    }
}

inline void built(int p, int l, int r){
    ta[p] = 0;
    if(l == r){
        sum[p] = 0;
        return;
    }
    int mid = (l + r) / 2;
    built(p * 2, l, mid);
    built(p * 2 + 1, mid + 1, r);
    pushup(p);
}

inline void update(int p, int l, int r, int s, int t){
    if(l >= s && t >= r){
        sum[p] = r - l + 1 - sum[p];
        ta[p] ^= 1;
        return;
    }
    pushdown(p, l, r);
    int mid = (l + r) / 2;
    if(mid >= s)update(p * 2, l, mid, s, t);
    if(mid < t)update(p * 2 + 1, mid + 1, r, s, t);
    pushup(p);
}

inline int getans(int p, int l, int r, int s, int t){
    if(l >= s && t >= r){
        return sum[p];
    }
    pushdown(p, l, r);
    int mid = (l + r) / 2;
    int ans = 0;
    if(mid >= s)ans += getans(p * 2, l, mid, s, t);
    if(mid < t)ans += getans(p * 2 + 1, mid + 1, r, s, t);
    return ans;
}

int main(){
    io;
    cin>>n>>m;
    built(1, 1, n);
    for(int i = 1; i <= m; ++i){
        cin>>op>>x>>y;
        if(op == 0){
            update(1, 1, n, x, y);
        }
        else{
            cout<<getans(1, 1, n, x, y)<<endl;
        }
    }
    return 0;
}

 

博客内容均系原创，未经允许严禁转载！
数据结构
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																					

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
势能线段树

							
							

							
trie树题单

							
							

							
01trie树

							
							

							
2022 CCPC Henan Provincial Collegiate Programming Contest「J – Mex Tree dfs序+ST表」

							
							

							
并查集——最优美的数据结构之一