线段树练习

P1198 [JSOI2008] 最大数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

// Problem: P1198 [JSOI2008] 最大数
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1198
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int maxn = 2e5 + 10;
#define int long long 
struct
{int l,r;int v;
}tr[maxn * 4];
void push_down(int u)
{tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}void built(int u,int l,int r)
{tr[u] = {l, r};if(l == r)return;//int mid = (l + r) >> 1;built(u << 1, l , mid);built(u << 1 | 1, mid + 1,r);
}void modify(int u,int x,int v)
{if(tr[u].l == x && tr[u].r == x)tr[u].v = v;else{int mid = (tr[u].l + tr[u].r) >> 1;if(x > mid)modify(u << 1 | 1,x , v);else modify(u << 1,x , v);push_down(u);}
}int query(int u, int l, int r)
{if(tr[u].l >= l && tr[u].r <= r)return tr[u].v; //int v = 0;int mid = tr[u].l + tr[u].r >> 1; //if(l <= mid)v = query(u << 1, l, r);if(r > mid)v = max(v, query(u << 1 | 1,l , r));return v;
}signed main()
{cin.tie(0) -> sync_with_stdio(false);int M, D;int n = 0;//队列数int last = 0;//最后一个数 cin >> M >> D;built(1, 1, M);//query modifywhile(M--){char key;int x;cin >> key >> x;if('A' == key){modify(1, ++n,(last + x) % D);}else{last = query(1,n - x + 1,n);cout << last << endl; }}return 0;
}

245. 你能回答这些问题吗 - AcWing题库

P3374 【模板】树状数组 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

// Problem: P3374 【模板】树状数组 1
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3374
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)//只有单点修改
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<string>
#include<cstring>
#include<cmath>
#include<bitset>
#include<sstream>//切割strtream头文件
#include<climits>//INT_MAX文件
#include <utility>
#include<memory>//for unique_ptr shared_ptr
using i64 = int64_t;
using namespace std;
#define int i64
#define endl '\n'
#define AC return 0;
#define WA(x) cout << x << endl;
#define lowbit(x) x & -x
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
int n, m, k, d, T = 1, A, B;template<typename T>void read(T &x) {T f = 1;x = 0;char s = getchar();while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();}while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();}x *= f;
}template<typename T>void print(T x) {if(x < 0) putchar('-'),x = -x;if(x > 9) print(x / 10);putchar(x % 10 + '0');putchar('\n');
}
constexpr int Init(int x)
{return x * 2;
}
int a[maxn];
struct node
{int l, r, sum;
}tr[maxn * 4];void pushdown(int u)
{tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}void built(int u,int l,int r)
{tr[u] = {l, r};if(l == r)return;else{int mid = (l + r) >> 1;built(u << 1, l, mid);built(u << 1 | 1, mid + 1, r);}
}void modify(int u, int x, int d)
{if(tr[u].l == x && tr[u].r == x)tr[u].sum += d;else{int mid = (tr[u].l + tr[u].r) >> 1;if(x <= mid)modify(u << 1, x, d);else modify(u << 1 | 1, x , d);pushdown(u);}
}int query(int u,int l,int r)
{if(tr[u].l >= l && tr[u].r <= r)return tr[u].sum;else{int mid = (tr[u].r + tr[u].l) >> 1;int res = 0;if(l <= mid)res += query(u << 1, l, r);if(r > mid)res += query(u << 1 | 1,l , r);return res;}
}void solve()
{auto x = make_unique<int>();cin >> n >> m;built(1, 1, n);for(int i = 1;i <= n;i++)cin >> a[i];for(int i = 1;i <= n;i++)modify(1, i, a[i]);for(int i = 1;i <= m;i++){cin >> k >> A >> B;if(1 == k)modify(1, A, B);elsecout << query(1, A, B) << endl;}}signed main() {cin.tie(0) -> sync_with_stdio(false);int T = 1;//read(T);while (T--) solve();return 0;
}

P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

// Problem: P3372 【模板】线段树 1
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3372
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<string>
#include<cstring>
#include<cmath>
#include<bitset>
#include<sstream>//切割strtream头文件
#include<climits>//INT_MAX文件
#include <utility>
#include<memory>//for unique_ptr shared_ptr
using i64 = int64_t;
using namespace std;
#define int i64
#define endl '\n'
#define AC return 0;
#define WA(x) cout << x << endl;
#define lowbit(x) x & -x
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
int n, m, k, d, T = 1, A, B;template<typename T>void read(T &x) {T f = 1;x = 0;char s = getchar();while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();}while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();}x *= f;
}template<typename T>void print(T x) {if(x < 0) putchar('-'),x = -x;if(x > 9) print(x / 10);putchar(x % 10 + '0');putchar('\n');
}
constexpr int Init(int x)
{return x * 2;
}
int a[maxn];
struct node
{int l, r, sum, add;	
}tr[maxn * 4];void pushup(int u)
{tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}void pushdown(int u)
{auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];if(root.add){left.add += root.add; left.sum += (left.r - left.l + 1) * root.add;right.add += root.add; right.sum += (right.r - right.l + 1) * root.add;root.add = 0;}
}void built(int u, int l, int r)
{if(l == r){tr[u] = {l, r, a[l], 0};return;}tr[u] = {l, r};int mid = (l + r) >> 1;built(u << 1, l, mid);built(u << 1 | 1, mid + 1, r);pushup(u);
}void modify(int u, int l, int r, int d)
{if(tr[u].l >= l && tr[u].r <= r){tr[u].sum += (tr[u].r - tr[u].l + 1) * d;tr[u].add += d;}else{pushdown(u);int mid = (tr[u].l + tr[u].r) >> 1;if(l <= mid)modify(u << 1, l, r, d);if(r > mid)modify(u << 1 | 1, l, r, d);pushup(u);}
}int query(int u, int l, int r)
{if(tr[u].l >= l && tr[u].r <= r)return tr[u].sum;pushdown(u);int mid = (tr[u].l + tr[u].r) >> 1;int res = 0;if(l <= mid)res += query(u << 1, l, r);if(r > mid)res += query(u << 1 | 1, l, r);return res;
}
void solve()
{auto x = make_unique<int>();cin >> n >> m;for(int i = 1;i <= n;i++)cin >> a[i];built(1, 1, n);while(m--){cin >> k >> A >> B;if(1 == k){int d;cin >> d;modify(1, A, B, d);}elsecout << query(1, A, B) << endl;}
}signed main() {cin.tie(0) -> sync_with_stdio(false);int T = 1;//read(T);while (T--) solve();return 0;
}

247. 亚特兰蒂斯 - AcWing题库

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;#define p1 (p<<1)
#define p2 (p<<1|1)const int N=10005;struct T {int l,r,mini,add;double len; //区间长度double minlen; //区间最小值的区间长度
} t[N*8];
struct A {double x,y1,y2;int add;
} a[N*2];
int n,len;
double lsh[N*2];bool cmp(A u,A v) {return u.x<v.x;}
int val(double x) {return lower_bound(lsh+1,lsh+1+len,x)-lsh;}
double raw(int x) {return lsh[x];}void pushUp(int p) {t[p].mini=min(t[p1].mini,t[p2].mini);double minlen=0;if(t[p].mini==t[p1].mini) minlen+=t[p1].minlen;if(t[p].mini==t[p2].mini) minlen+=t[p2].minlen;t[p].minlen=minlen;
}void build(int p,int l,int r) {double len=raw(r+1)-raw(l);t[p]={l,r,0,0,len,len};if(l==r) return;int mid=l+r>>1;build(p1,l,mid),build(p2,mid+1,r);
}void pushDown(int p) {t[p1].add+=t[p].add,t[p2].add+=t[p].add;t[p1].mini+=t[p].add,t[p2].mini+=t[p].add;t[p].add=0;
}void upd(int p,int l,int r,int add) {if(t[p].l>=l && t[p].r<=r) {t[p].mini+=add,t[p].add+=add; return;}if(t[p].add!=0) pushDown(p);int mid=t[p].l+t[p].r>>1;if(l<=mid) upd(p1,l,r,add);if(r>mid) upd(p2,l,r,add);pushUp(p);
}int main()
{for(int tim=1;;tim++) {scanf("%d",&n);if(!n) break;printf("Test case #%d\n",tim);for(int i=1;i<=n;i++) {double x1,y1,x2,y2;scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);a[i]={x1,y1,y2,1},a[i+n]={x2,y1,y2,-1};lsh[i]=y1,lsh[i+n]=y2;}n*=2;sort(a+1,a+1+n,cmp),sort(lsh+1,lsh+1+n);len=unique(lsh+1,lsh+1+n)-lsh-1;build(1,1,len-1);double ans=0;upd(1,val(a[1].y1),val(a[1].y2)-1,a[1].add);for(int i=2;i<=n;i++) {double len=t[1].len;if(!t[1].mini) len-=t[1].minlen;ans+=len*(a[i].x-a[i-1].x);upd(1,val(a[i].y1),val(a[i].y2)-1,a[i].add);}printf("Total explored area: %.2lf\n\n",ans);}return 0;
}

线段树扫描线应用

P3373 【模板】线段树 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

// Problem: P3373 【模板】线段树 2
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3373
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<string>
#include<cstring>
#include<cmath>
#include<bitset>
#include<sstream>//切割strtream头文件
#include<climits>//INT_MAX文件
#include <utility>
#include<memory>//for unique_ptr shared_ptr
using i64 = int64_t;
using namespace std;
#define int i64
#define endl '\n'
#define AC return 0;
#define WA(x) cout << x << endl;
#define lowbit(x) x & -x
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
int n, m, k, d, T = 1, A, B, p;template<typename T>void read(T &x) {T f = 1;x = 0;char s = getchar();while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();}while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();}x *= f;
}template<typename T>void print(T x) {if(x < 0) putchar('-'),x = -x;if(x > 9) print(x / 10);putchar(x % 10 + '0');putchar('\n');
}
constexpr int Init(int x)
{return x * 2;
}
int a[maxn];struct node
{int l, r, sum, add, mul;
}tr[maxn];void eval(node &root,int add, int mul)
{root.sum = (root.sum * mul + ((root.r - root.l + 1) * add)) % p;root.mul = root.mul * mul % p;root.add = (root.add * mul + add) % p;
}void pushup(int u)
{tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % p;
}void pushdown(int u)
{eval(tr[u << 1],tr[u].add, tr[u].mul);eval(tr[u << 1 | 1],tr[u].add, tr[u].mul);tr[u].add = 0;tr[u].mul = 1;
}void built(int u, int l, int r)
{if(l == r)tr[u] = {l, r, a[l], 0, 1};else{tr[u] = {l, r, 0, 0 , 1};int mid = (l + r) >> 1;built(u << 1, l, mid);built(u << 1 | 1,mid + 1, r);pushup(u);}
}void modify(int u, int l, int r, int add, int mul)
{if(tr[u].l >= l && tr[u].r <= r)eval(tr[u], add, mul);else{pushdown(u);int mid = (tr[u].l + tr[u].r) >> 1;if(l <= mid)modify(u << 1, l, r, add, mul);if(r > mid)modify(u << 1 | 1, l, r, add, mul);pushup(u);}
}int query(int u, int l, int r)
{if(tr[u].l >= l && tr[u].r <= r)return tr[u].sum % p;pushdown(u);int mid = (tr[u].l + tr[u].r) >> 1;int res = 0;if(l <= mid)res += query(u << 1, l, r) % p;if(r > mid)res += query(u << 1 | 1, l, r) % p;return res % p;
}void solve()
{auto x = make_unique<int>();cin >> n >> m >> p;for(int i = 1;i <= n;i++)cin >> a[i];built(1, 1, n);while(m--){cin >> k >> A >> B;if(3 == k)cout << query(1, A, B) << endl;else{int d; cin >> d;k == 1 ? modify(1, A, B, 0, d) : modify(1, A, B, d, 1);}}
}signed main() {cin.tie(0) -> sync_with_stdio(false);int T = 1;//read(T);while (T--) solve();return 0;
}