势能线段树 – Suryxin's Blog

板子

inline void pushup(int p){
    sum[p] = (sum[ls] + sum[rs]) % mod;//更新sum
    dio[p] = dio[ls] & dio[rs];//更新标记
}

inline void built(int p, int l, int r){
    if(l == r){
      //更新sum、标记、懒标记等
        return;
    }
    int mid = (l + r) / 2;
    built(ls, l, mid);
    built(rs, mid + 1, r);
    pushup(p);
}

inline void lazy_cal(int p, ll c){//计算懒标记产生的价值
    sum[p] = (sum[p] * c) % mod;
    la[p] = (la[p] * c) % mod;
}

inline void pushdown(int p){//标记下传
    if(la[p] != 1){
        lazy_cal(ls, la[p]);
        lazy_cal(rs, la[p]);
        la[p] = 1;
    }
}

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

inline void update(int p, int l, int r, int s, int t, int id, int num){
    if(s <= l && r <= t && dio[p][id]){//整个区间的更新
        for(int i = 1; i <= num; ++i)lazy_cal(p, pri[id]);
        return;
    }
    if(l == r){//单点更新
        lazy_cal(p, pri[id] - 1);
        for(int i = 1; i < num; ++i)lazy_cal(p, pri[id]);
        dio[p][id] = 1;
        return;
    }
    pushdown(p);
    int mid = (l + r) / 2;
    if(mid >= s)update(ls, l, mid, s, t, id, num);
    if(mid < t)update(rs, mid + 1, r, s, t, id, num);
    pushup(p);
}

势能线段树模板题一

题目描述：

对区间进行开根号及向下取整操作

求区间和

思路：

所有数字开根号的势能上限都是6，也就是说最多开6次，就会变成1，然后就可以用势能线段树写了

定义区间开根次数cnt为势能，势能初始值为势能上限=6，定义0势能点为cnt=0

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define MAX 200000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(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 slll(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))
#define m_p(a,b) make_pair(a, b)

typedef  long long ll;
typedef pair <int,int> pii;
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;
ll x, y, op;
ll sum[4 * MAX];
ll num[4 * MAX];
ll tr[MAX];

inline void pushup(ll p){
    sum[p] = sum[ls] + sum[rs];
    num[p] = min(num[ls], num[rs]);
}

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

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

inline void update(ll p, ll l, ll r, ll s, ll t){
    if(num[p] > 5)return;
    if(l == r){
        ++num[p];
        sum[p] = sqrt(sum[p]);
        return;
    }
    ll mid = (l + r) / 2;
    if(mid >= s)update(ls, l, mid, s, t);
    if(mid < t)update(rs, mid + 1, r, s, t);
    pushup(p);
}

void work()
{
    sll(n, m);
    for(int i = 1; i <= n; ++i)sl(tr[i]);
    built(1, 1, n);
    for(int i = 1; i <= m; ++i){
        sl(op);
        if(op == 1){
            sll(x, y);
            update(1, 1, n, x, y);
        }
        else{
            sll(x, y);
            cout<<getans(1, 1, n, x, y)<<endl;
        }
    }
}

int main(){
//    int tt;cin>>tt;
//    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
//    }
    return 0;
}

势能线段树模板题二

题目描述：

给定区间[l,r]{[l,r]}[l,r]对区间中所有数字开根号向下取整，即 $ai=⌊ai⌋(l≤i≤r)a_i= \lfloor \sqrt{a_i} \rfloor(l \leq i \leq r)ai=⌊ai⌋(l≤i≤r)$

给定区间[l,r]，对区间中每个数字加上一个正整数 $x$ 。

查询给定区间[l,r]的元素和，即求 $∑i=lrai\sum_{i=l}^{r}a_{i}∑i=lrai。$

思路：

这个题和上面的题不一样的地方是发生了势能重置

定义区间最大值max与区间最小值min的差值diff为势能，势能初始值为差值diff，定义0势能点为diff=0。

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define MAX 200000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(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 slll(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))
#define m_p(a,b) make_pair(a, b)

typedef  long long ll;
typedef pair <int,int> pii;
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;
ll x, y, op, k;
ll sum[4 * MAX];
ll minx[4 * MAX], maxn[4 * MAX];
ll tr[MAX];
ll la[4 * MAX];

inline void pushup(ll p){
    sum[p] = sum[ls] + sum[rs];
    minx[p] = min(minx[ls], minx[rs]);
    maxn[p] = max(maxn[ls], maxn[rs]);
}

inline void lazy_cal(ll p, ll len, ll c){
    sum[p] += c * len;
    la[p] += c;
    minx[p] += c;
    maxn[p] += c;
}

inline void pushdown(ll p, ll len){
    if(la[p]){
        lazy_cal(ls, len - len / 2, la[p]);
        lazy_cal(rs, len / 2, la[p]);
        la[p] = 0;
    }
}

inline void built(ll p, ll l, ll r){
    if(l == r){
        sum[p] = minx[p] = maxn[p] = tr[l];
        return;
    }
    ll mid = (l + r) / 2;
    built(ls, l, mid);
    built(rs, mid + 1, r);
    pushup(p);
}


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

inline void update(ll p, ll l, ll r, ll s, ll t, ll c){
    if(s <= l && r <= t && (c != -1 || minx[p] == maxn[p])){
        if(c == -1){
            sum[p] = (r - l + 1) * (ll)sqrt(minx[p]);
            la[p] -= minx[p] - (ll)sqrt(minx[p]);
            minx[p] = maxn[p] = (ll)sqrt(minx[p]);
        }
        else{
            lazy_cal(p, r - l + 1, c);
        }
        return;
    }
    pushdown(p, r - l + 1);
    ll mid = (l + r) / 2;
    if(mid >= s)update(ls, l, mid, s, t, c);
    if(mid < t)update(rs, mid + 1, r, s, t, c);
    pushup(p);
}

void work()
{
    sll(n, m);
    for(int i = 1; i <= n; ++i)sl(tr[i]);
    built(1, 1, n);
    for(int i = 1; i <= m; ++i){
        sl(op);
        if(op == 1){
            sll(x, y);
            update(1, 1, n, x, y, -1);
        }
        else if(op == 2){
            slll(x, y, k);
            update(1, 1, n, x, y, k);
        }
        else{
            sll(x, y);
            cout<<getans(1, 1, n, x, y)<<endl;
        }
    }
}

int main(){
//    int tt;cin>>tt;
//    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
//    }
    return 0;
}

Lowbit

题目描述：

对区间所有值加上其lowbit

求区间和

思路：

一个数加一次lowbit就会使得最后一个1加1，往前进1位

没加几次就会变成类似10000这样的二进制数，此时加上lowbit，就相当于乘以2，所以我们懒标记标记的就是乘2的次数，如果整个区间都是1000这样的二进制数，就打上标记

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define MAX 200000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 998244353
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(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 slll(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))
#define m_p(a,b) make_pair(a, b)

typedef  long long ll;
typedef pair <int,int> pii;
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;
ll x, y, op;
ll tr[4 * MAX];
ll la[4 * MAX];
ll sum[4 * MAX];
int vis[4 * MAX];

inline bool judge(ll x){
    return !(x & (x - 1));
}

ll q_pow(ll a, ll b){
    ll ans = 1;
    while(b > 0){
        if(b & 1)ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

inline void pushup(ll p){
    sum[p] = (sum[ls] + sum[rs]) % mod;
    vis[p] = vis[ls] & vis[rs];
}

inline void lazy_cal(ll p, ll c){
    sum[p] = (sum[p] * q_pow(2, c)) % mod;
    la[p] += c;
}

inline void pushdown(ll p){
    if(la[p]){
        lazy_cal(ls, la[p]);
        lazy_cal(rs, la[p]);
        la[p] = 0;
    }
}

inline void built(ll p, ll l, ll r){
    if(l == r){
        sum[p] = tr[l];
        if(judge(sum[p]))vis[p] = 1;
        return;
    }
    ll mid = (l + r) / 2;
    built(ls, l, mid);
    built(rs, mid + 1, r);
    pushup(p);
}

inline void update(ll p, ll l, ll r, ll s, ll t){
    if(s <= l && r <= t && vis[p]){
        lazy_cal(p, 1);
        return;
    }
    if(l == r){
        sum[p] += lowbit(sum[p]);
        if(judge(sum[p]))vis[p] = 1;
        return;
    }
    pushdown(p);
    ll mid = (l + r) / 2;
    if(mid >= s)update(ls, l, mid, s, t);
    if(mid < t)update(rs, mid + 1, r, s, t);
    pushup(p);
}

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

inline void init(){
    mem(tr, 0);
    mem(sum, 0);
    mem(vis, 0);
    mem(la, 0);
}

void work(){
    sl(n);
    for(int i = 1; i <= n; ++i)sl(tr[i]);
    built(1, 1, n);
    sl(m);
    for(int i = 1; i <= m; ++i){
        slll(op, x, y);
        if(op == 1){
            update(1, 1, n, x, y);
        }
        else{
            cout<<getans(1, 1, n, x, y)<<endl;
        }
    }
    
}

int main(){
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        init();
//        printf("Case #%d: ", _t);
        work();
    }
    return 0;
}

Euler Function

题目描述：

区间[l, r]乘以x

求区间[l, r]的欧拉函数值

思路：

if(y是素数){
if(x % y == 0)f[x*y] = f[x] * y;
else f[x*y] = f[x] * (y - 1);
}
每次乘的数是小于等于100的，而根据唯一分解定理，每个数都可以分解成若干个素数的乘积，这样就可以将要乘的数化为若干次乘素数的过程，如果一个区间都是一个素数的倍数，那区间欧拉就可以直接用区间乘以这个素数即可，如果不是，就乘一次就可以变成这个素数的倍数，如果再乘这个东西，那欧拉值就可以直接乘这个素数了

所以标记就是这个数是不是某个素数的倍数

用bitset来维护即可

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define MAX 100000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 998244353
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define seed 1331
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(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))
#define m_p(a,b) make_pair(a, b)

typedef  long long ll;
typedef pair <int,int> pii;
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;
int op, x, y, c;
int np;
int pri[105];
int cnt[105][30];
bitset<30>st[105];
int f[105];
ll tr[MAX];
ll sum[4 * MAX];
ll la[4 * MAX];
bitset<30>dio[4 * MAX];

inline int phi(int x)
{
    int s=x,i=2;
    for (;i*i<=x;i++) if (!(x%i)) {s=s/i*(i-1); for (;!(x%i);x/=i);}
    if (x>1) s=s/x*(x-1); return s;
}

void init(){
    f[1] = 1;
    for(int i = 2; i <= 100; ++i){
        f[i] = phi(i);
        bool k = 0;
        for(int j = 2; j < i; ++j){
            if(i % j == 0){
                k = 1;
                break;
            }
        }
        if(!k)pri[++np] = i;
    }
    for(int i = 1; i <= 100; ++i){
        for(int j = 1; j <= 25; ++j){
            int a = i, b = pri[j];
            while (a % b == 0) {
                a /= b;
                ++cnt[i][j];
            }
            st[i][j] = cnt[i][j];
        }
    }
}

inline void pushup(int p){
    sum[p] = (sum[ls] + sum[rs]) % mod;
    dio[p] = dio[ls] & dio[rs];
}


inline void built(int p, int l, int r){
    la[p] = 1;
    if(l == r){
        sum[p] = f[tr[l]] % mod;
        dio[p] = st[tr[l]];
        return;
    }
    int mid = (l + r) / 2;
    built(ls, l, mid);
    built(rs, mid + 1, r);
    pushup(p);
}

inline void lazy_cal(int p, ll c){
    sum[p] = (sum[p] * c) % mod;
    la[p] = (la[p] * c) % mod;
}

inline void pushdown(int p){
    if(la[p] != 1){
        lazy_cal(ls, la[p]);
        lazy_cal(rs, la[p]);
        la[p] = 1;
    }
}

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

inline void update(int p, int l, int r, int s, int t, int id, int num){
    if(s <= l && r <= t && dio[p][id]){
        for(int i = 1; i <= num; ++i)lazy_cal(p, pri[id]);
        return;
    }
    if(l == r){
        lazy_cal(p, pri[id] - 1);
        for(int i = 1; i < num; ++i)lazy_cal(p, pri[id]);
        dio[p][id] = 1;
        return;
    }
    pushdown(p);
    int mid = (l + r) / 2;
    if(mid >= s)update(ls, l, mid, s, t, id, num);
    if(mid < t)update(rs, mid + 1, r, s, t, id, num);
    pushup(p);
}


void work(){
    init();
    sdd(n, m);
    for(int i = 1; i <= n; ++i)sl(tr[i]);
    built(1, 1, n);
    for(int i = 1; i <= m; ++i){
        sd(op);
        if(op == 0){
            sddd(x, y, c);
            for(int j = 1; j <= 25; ++j){
                if(st[c][j])update(1, 1, n, x, y, j, cnt[c][j]);
            }
        }
        else{
            sdd(x, y);
            cout<<getans(1, 1, n, x, y)<<endl;
        }
    }
}

int main(){
//    int tt;cin>>tt;
//    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
//    }
    return 0;
}

妄想集合

题目描述：

开始有 n 个可重集合，开始时每一个集合中都有一个数，有 m个操作。

往编号在 l∼r 的每个集合中加入一个数 x

询问能否从 l∼r 的集合中取出三个数使得他们能作为边长组成一个三角形（即最小两个和要大于最大的）。

思路1：

当数列中的所有数都是斐波那契数列中的数的时候，任意三个数不能组成三角形

根据上述理论，我们可以计算一下发现1e9中只有44个斐波那契数

那再根据鸽巢原理，如果一个集合的数量大于44，就说明肯定会满足至少存在一种情况使的从中取出来三个数能组成三角形

所以我们可以考虑使用势能线段树，维护一个标记数组，表示线段树的上的区间的数的数量是否大于44，再维护一个num数组，维护区间集合的数字的总数量

因为一个集合最多加44个数就可以了，所以在这之前就暴力修改，大于44后就给标记值更新，表明这个区间此后不用再更新了，查询的时候就查询l到r的集合的num是否大于44即可，如果没有就暴力判断，将[l,r]的集合的所有元素都扔进一个vector，排序以后暴力判断

当然，那个标记数组可以通过维护区间最小值来代替，不过bool来说会快点，所以就用了

/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mid ((l + r)>>1)
#define mod 425
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(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 slll(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))
#define m_p(a,b) make_pair(a, b)
typedef  long long ll;
//typedef pair <int,int> pii;
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;}

#define MAX 100000 + 10
int n, k, m, x, y, z, q, p;
bool tmp;
string op;
int s;

vector<int>v[MAX];
int num[4 * MAX];
bool vis[4 * MAX];

inline void pushup(int p){
    num[p] = num[ls] + num[rs];
    vis[p] = vis[ls] & vis[rs];
}

void built(int p, int l, int r){
    if(l == r){
        num[p] = 1;
        vis[p] = 0;
        return;
    }
    int mid = (l + r) / 2;
    built(ls, l, mid);
    built(rs, mid + 1, r);
    pushup(p);
}

void update(int p, int l, int r, int s, int t, int c){
    if(s <= l && r <= t && vis[p]){
        return;
    }
    if(l == r){
        num[p] += 1;
        if(num[p] >= 46)vis[p] = 1;
        v[l].push_back(c);
        return;
    }
    int mid = (l + r) / 2;
    if(mid >= s)update(ls, l, mid, s, t, c);
    if(mid < t)update(rs, mid + 1, r, s, t, c);
    pushup(p);
}

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


void work()
{
    cin>>n>>m;
    for(int i = 1; i <= n; ++i){
        cin>>x;
        v[i].push_back(x);
        num[i] = 1;
    }
    built(1, 1, n);
    for(int i = 1; i <= m; ++i){
        cin>>op;
        if(op[0] == 'A'){
            cin>>x>>y;
            p = getans(1, 1, n, x, y);
            if(p < 3){
                cout<<"NO\n";
            }
            else if(p >= 56){
                cout<<"YES\n";
            }
            else{
//                cout<<p<<endl;
                vector<int>san;
                for(int i = x; i <= y; ++i){
                    for(int j = 0; j < v[i].size(); ++j){
                        san.push_back(v[i][j]);
                    }
                }
                sort(san.begin(), san.end());
                tmp = 0;
                for(int i = 0; i < san.size() - 2; ++i){
                    if(san[i] + san[i + 1] > san[i + 2]){
                        tmp = 1;
                        break;
                    }
                }
                if(tmp){
                    cout<<"YES\n";
                }
                else cout<<"NO\n";
            }
        }
        else{
            cin>>x>>y>>z;
            update(1, 1, n, x, y, z);
        }
    }
}

int main(){
    io;
//    int tt;cin>>tt;
//    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
//    }
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}

板子

势能线段树模板题一

题目描述：

思路：

势能线段树模板题二

题目描述：

思路：

Lowbit

题目描述：

思路：

Euler Function

题目描述 ：

思路：

妄想集合

题目描述：

思路1：

发送评论 编辑评论

推荐文章

题目描述：

发送评论编辑评论