- 单点修改,区间查询
给n个数a1,a2,a3,…,an。
支持q个操作:
-
1 x d
,修改ax=d。 -
2 l r
,查询(l,r),并且求出最小值出现了多少次。
输入格式
第一行两个整数n,q(1≤n,q≤2×105)。
接下来一行n个整数a1,a2,…,an(1≤ai≤109)。
接下来q行,每行一个形如1 x d
或者2 l r
的操作,保证1≤x≤n,1≤l≤r≤n,1≤d≤109
输出格式
对于每个查询,输出一行两个数,分别表示最小值和出现的次数。
样例输入
5 5
1 2 3 4 5
2 4 5
1 5 1
2 1 5
1 2 3
2 2 4
样例输出
4 1
1 2
3 2
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e6 + 10; int n,m; int a[N]; struct now{ int cnt; int num; }; now seg[N]; void update(int idx) { if(seg[idx*2].num > seg[idx*2+1].num) { seg[idx] = seg[idx*2+1]; } else if(seg[idx*2].num < seg[idx*2+1].num) { seg[idx] = seg[idx*2]; } else { seg[idx].num = seg[idx*2].num; seg[idx].cnt = seg[idx*2].cnt + seg[idx*2+1].cnt; } } void build(int idx,int l,int r) { if(l == r) { seg[idx] = {1,a[l]}; } else { int mid = (l+r)/2; build(idx*2,l,mid); build(idx*2+1,mid+1,r); update(idx); } } void modify(int idx,int l,int r,int id,int val) { if(l == r) { seg[idx] = {1,val}; } else { int mid = (l+r)/2; if(mid < id) modify(idx*2+1,mid+1,r,id,val); else modify(idx*2,l,mid,id,val); update(idx); } } now query(int idx,int l,int r,int ql,int qr) { now ans = {0LL,(int)1e18}; if(l == ql && r == qr) { return seg[idx]; } else { int mid = (l+r)/2; if(qr<=mid) { auto w = query(idx*2,l,mid,ql,qr); if(w.num < ans.num) ans = w; else if(w.num == ans.num) ans.cnt += w.cnt; } else if(ql > mid) { auto w = query(idx*2+1,mid+1,r,ql,qr); if(w.num < ans.num) ans = w; else if(w.num == ans.num) ans.cnt += w.cnt; } else { auto w = query(idx*2,l,mid,ql,mid); auto v = query(idx*2+1,mid+1,r,mid+1,qr); if(w.num < ans.num) ans = w; else if(w.num == ans.num) ans.cnt += w.cnt; if(v.num < ans.num) ans = v; else if(v.num == ans.num) ans.cnt += v.cnt; } return ans; } } void solve() { cin >> n >> m; for(int i = 1;i <= n;i ++) cin >> a[i]; build(1,1,n); for(int i = 1;i <= m;i ++) { int op,x,y; cin >> op >> x >> y; if(op == 1) { modify(1,1,n,x,y); } else { auto c = query(1,1,n,x,y); cout << c.num << ' ' << c.cnt << '\n'; } } } signed main() { solve(); }panyu
- 最大子段和
给n个数a1,a2,a3,…,an。
支持q个操作:
-
1 x d
,修改ax=d。 -
2 l r
,查询[l,r]中的最大子段和,也就是找到l≤l′≤r′≤r,使得(l,r)的和最大。
输入格式
第一行两个整数n,q(1≤n,q≤2×105)。
接下来一行n个整数a1,a2,…,an(−109≤ai≤109)。
接下来q行,每行一个形如1 x d
或者2 l r
的操作,保证1≤x≤n,1≤l≤r≤n,−109≤d≤109。
输出格式
对于每个查询,输出一行,表示答案。
样例输入
5 5
-1 2 -3 4 -5
2 4 5
1 2 4
2 1 5
1 4 -1
2 2 4
样例输出
4
5
4
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5 + 10; ll n,q; ll a[N]; struct Now{ ll mas; ll maspre; ll massuf; ll ans; }seg[4*N]; void update(int id) { seg[id].mas = seg[id*2].mas + seg[id*2+1].mas; seg[id].maspre = max(seg[id*2].maspre,seg[id*2+1].maspre + seg[id*2].mas); seg[id].massuf = max(seg[id*2].massuf + seg[id*2+1].mas,seg[id*2+1].massuf); seg[id].ans = max(max(seg[id*2].ans,seg[id*2+1].ans),seg[id*2].massuf+seg[id*2+1].maspre); } void build(ll id,ll l,ll r) { if(l == r) { seg[id].ans = a[l]; seg[id].mas = a[l]; seg[id].maspre = a[l]; seg[id].massuf = a[l]; return ; } ll mid = (l+r)>>1; build(id*2,l,mid); build(id*2+1,mid + 1,r); update(id); } void modify(ll id ,ll l,ll r,ll res,ll val) { if(l == r && l == res) { seg[id].mas = val; seg[id].maspre = val; seg[id].massuf = val; seg[id].ans = val; return ; } ll mid = (l+r)>>1; if(res <= mid) modify(id*2,l,mid,res,val); else modify(id*2+1,mid+1,r,res,val); update(id); } Now query(ll id,ll l,ll r,ll lx,ll rx) { if(lx <= l && r <= rx) { return seg[id]; } ll mid = (l+r)>>1; if(rx <= mid) return query(id*2,l,mid,lx,rx); else if(lx > mid) return query(id*2+1,mid+1,r,lx,rx); else { Now b,c,d; b = query(id*2,l,mid,lx,rx); c = query(id*2+1,mid+1,r,lx,rx); //b.mas+c.mas, d.mas = b.mas + c.mas; d.maspre = max(b.maspre,c.maspre + b.mas); d.massuf = max(b.massuf + c.mas,c.massuf); d.ans = max(max(b.ans,c.ans),b.massuf+c.maspre); return d; } //(query(id*2+1,mid+1,r,lx,rx)+query(id*2,l,mid,lx,rx)); } int main() { scanf("%lld %lld",&n,&q); for(int i = 1; i <= n;i ++) scanf("%lld",&a[i]); build(1,1,n); while(q--) { int ty; scanf("%d",&ty); if(ty == 1) { ll x,y; scanf("%lld %lld",&x,&y); modify(1,1,n,x,y); } else { ll x,y; scanf("%lld %lld",&x,&y); printf("%lld\n",query(1,1,n,x,y).ans); } } }panyu
- 区间修改,区间查询(懒标记)
给n个数a1,a2,a3,…,an。
支持q个操作:
-
1 l r d
,令所有的ai(l≤i≤r))ai(l≤i≤r)加上d。 -
2 l r
,查询(l,r)的最大值。
输入格式
第一行两个整数n,q(1≤n,q≤2×105)。
接下来一行n个整数a1,a2,…,an(1≤ai≤109)。
接下来q行,每行一个形如1 l r d
或者2 l r
的操作,保证1≤l≤r≤n,1≤d≤109。
输出格式
对于每个查询,输出一行,表示答案。
样例输入
5 5
1 2 3 4 5
2 4 5
1 1 5 1
2 1 4
1 2 3 10
2 2 4
样例输出
5
5
14
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e6 + 10; int n,m; int a[N]; struct now{ int cnt; int num; }; int seg[N*4]; int teg[4*N]; void update(int idx) { seg[idx] = max(seg[idx*2],seg[idx*2+1]); } void pushdown(int idx,int l,int r) { int mid = (l+r)/2; seg[idx*2] += teg[idx]; seg[idx*2+1] += teg[idx]; teg[idx*2] += teg[idx]; teg[idx*2+1] += teg[idx]; teg[idx] = 0; } void build(int idx,int l,int r) { if(l == r) { seg[idx] = a[l]; } else { int mid = (l+r)/2; build(idx*2,l,mid); build(idx*2+1,mid+1,r); update(idx); } } void modify(int idx,int l,int r,int ql,int qr,int val) { if(ql <= l && qr >= r) { seg[idx] += val; teg[idx] += val; } else { pushdown(idx,l,r); int mid = (l+r)/2; if(mid < qr) modify(idx*2+1,mid+1,r,ql,qr,val); if(mid >= ql) modify(idx*2,l,mid,ql,qr,val); update(idx); } } int query(int idx,int l,int r,int ql,int qr) { int ans = 0; if(l >= ql && r <= qr) { //cout <<seg[idx] << '\n'; return seg[idx]; } else { pushdown(idx,l,r); int mid = (l+r)/2; if(mid < qr) ans = max(ans,query(idx*2+1,mid+1,r,ql,qr)); if(mid >= ql) ans = max(ans,query(idx*2,l,mid,ql,qr)); return ans; } } void solve() { cin >> n >> m; for(int i = 1;i <= n;i ++) cin >> a[i]; build(1,1,n); for(int i = 1;i <= m;i ++) { int op,x,y; cin >> op >> x >> y; if(op == 1) { int d; cin >> d; modify(1,1,n,x,y,d); } else { int c = query(1,1,n,x,y); cout << c << '\n'; } } } signed main() { solve(); }panyu
- 线段树二分
给n个数a1,a2,a3,…,an1,2,3,…,。
支持q个操作:
-
1 x d
,修改ax=d。 -
2 l r d
, 查询al,al+1,al+2,…,ar中大于等于d的第一个数的下标,如果不存在,输出−1。也就是说,求最小的i(l≤i≤r)满足ai≥d。
输入格式
第一行两个整数n,q(1≤n,q≤2×105)。
接下来一行n个整数a1,a2,…,an(1≤ai≤109)。
接下来q行,每行一个形如1 x d
或者2 l r d
的操作,保证1≤x≤n,1≤l≤r≤n,1≤d≤109。
输出格式
对于每个查询,输出一行,表示答案。
样例输入
5 5
1 2 3 4 5
2 4 5 5
1 5 1
2 1 5 3
1 3 2
2 1 3 3
样例输出
5
3
-1
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 201000; int n, q; int a[N]; struct node { int val; } seg[N * 4]; // [l, r] void update(int id) { seg[id].val = max(seg[id * 2].val, seg[id * 2 + 1].val); } void build(int id, int l, int r) { if (l == r) { seg[id].val = a[l]; } else { int mid = (l + r) / 2; build(id * 2, l, mid); build(id * 2 + 1, mid + 1, r); update(id); } } // 节点为id,对应的区间为[l, r],修改a[pos] -> val void change(int id, int l, int r, int pos, int val) { if (l == r) { seg[id].val = val; } else { int mid = (l + r) / 2; if (pos <= mid) change(id * 2, l, mid, pos, val); else change(id * 2 + 1, mid + 1, r, pos, val); // 重要‼️ update(id); } } int search(int id, int l, int r, int ql, int qr, int d) { if (l == ql && r == qr) { if (seg[id].val < d) return -1; else { if (l == r) return l; int mid = (l + r) / 2; if (seg[id * 2].val >= d) return search(id * 2, l, mid, ql, mid, d); else return search(id * 2 + 1, mid + 1, r, mid + 1, qr, d); } } int mid = (l + r) / 2; // [l, mid] , [mid + 1, r] if (qr <= mid) return search(id * 2, l, mid, ql, qr, d); else if (ql > mid) return search(id * 2 + 1, mid + 1, r, ql, qr, d); else { int pos = search(id * 2, l, mid, ql, mid, d); if (pos == -1) return search(id * 2 + 1, mid + 1, r, mid + 1, qr, d); else return pos; } } int main() { scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } build(1, 1, n); for (int i = 0; i < q; i++) { int ty; scanf("%d", &ty); if (ty == 1) { int x, d; scanf("%d%d", &x, &d); change(1, 1, n, x, d); } else { int l, r, d; scanf("%d%d%d", &l, &r, &d); auto ans = search(1, 1, n, l, r, d); printf("%d\n", ans); } } }panyu
标签:idx,int,线段,mid,seg,ans,id,模板
From: https://www.cnblogs.com/ljmxmu/p/17555530.html