线段树维护区间信息的题单
dalao的博客
最长区间
带修改的严格最长上升子序列长度。【练习线段树做法】
要深入理解线段树的l, r是指的数组下标这句话emm.
一个节点保存：左边的LIS长度， 右边的LIS长度， 区间总体的LIS长度， 区间的元素个数（其实可以算出来）。
关键在于pushup函数：
先更新区间的llis,rlis,tlis.
然后如果左边最右的值<右边最左的值（这个可以用线段树中节点在数组的下标实现，因为l,r指的是下标）：那左右两个区间就可以构成lis,所以可以继续更新：
如果左边的llis==左边的size，代表左边整个是一个最长上升子序列，那llis就可以更新；同理rlis也可以。
最后更新tlis可以是左边的rlis和右边的llis。
tips:可以与LCIS这个题比较一下， 其实这样直接query对于一般区间是不对的，不能简单左右区间答案相加，（例如1 2 3 4 1 2， 查询1到5，并不是4+1）。但是这个题一定是询问1到n的区间，所以可以直接加。
#include
#define ll long long
using namespace std;
const int N = 100010;
int n,m,w[N];
struct node{
int l, r, llis,rlis,tlis, sz;
}tr[N << 2];
void pushup(int u){
tr[u].sz = tr[u << 1].sz + tr[u << 1 | 1].sz;
tr[u].llis = tr[u << 1].llis;
tr[u].rlis = tr[u << 1 | 1].rlis;
tr[u].tlis = max(tr[u << 1].tlis, tr[u << 1 | 1].tlis);
if(w[tr[u << 1].r] < w[tr[u << 1 | 1].l]){ //严格单调增
int mid = tr[u].l + tr[u].r >> 1;
if(tr[u << 1].llis == tr[u << 1].sz) //左边整体严格单调增
tr[u].llis += tr[u << 1 | 1].llis;
if(tr[u << 1 | 1].rlis == tr[u << 1 | 1].sz)
tr[u].rlis += tr[u << 1].rlis;
tr[u].tlis = max(tr[u].tlis, tr[u << 1].rlis + tr[u << 1 | 1].llis);
}
}
void build(int u, int l, int r){
tr[u]= {l, r, 1, 1, 1, 1};
if(l == r) return ;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void modify(int u, int x, int v){
if(tr[u].l == tr[u].r){
w[x] = v;
return ;
}
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
int query(int u, int l, int r){
if(tr[u].l >= l && tr[u].r <= r) return tr[u].tlis;
int mid = tr[u].l + tr[u].r >> 1;
int res = 0;
if(l <= mid) res += query(u << 1, l, mid);
if(r > mid) res += query(u << 1 | 1, mid + 1, r);
return res;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; ++ i) scanf("%d", &w[i]);
build(1, 1, n);
printf("%d\n", query(1, 1, n));
while(m --){
int x, v;
scanf("%d%d",&x,&v);
modify(1, x, v);
printf("%d\n", query(1, 1, n));
}
return 0;
}Tunnel Warfare 【线段树区间合并】
几乎是模板题，用这个题来开始线段树区间合并再好不过。 待补充Qwq 2021.4.11没写完
注意pushup和query函数， 并不是和最普通的线段树一样的。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
#define ll long long
#define ls lmax
#define rs rmax
#define ms tmax
#define len sum
#define Tree tr
using namespace std;
const int N = 50010;
int n,m,w[N];
stack<int> distory;
struct node{
int l, r,lmax,rmax,tmax,sum; //维护左边右边全部的连续1的个数,区间长度
}tr[N << 2];
void pushup(int u){
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
tr[u].lmax = tr[u << 1].lmax, tr[u].rmax = tr[u << 1 | 1].rmax, tr[u].tmax = max(tr[u << 1].tmax, tr[u << 1 | 1].tmax);
if(w[tr[u << 1].r] == 1){
if(tr[u << 1].lmax == tr[u << 1].sum) tr[u].lmax += tr[u << 1 | 1].lmax;
if(tr[u << 1 | 1].rmax == tr[u << 1 | 1].sum) tr[u].rmax += tr[u << 1].rmax;
tr[u].tmax = max(tr[u].tmax, tr[u << 1].rmax + tr[u << 1 | 1].lmax);
}
}
void build(int u, int l, int r){
int tmp = r - l + 1;
tr[u] = {l, r, tmp, tmp, tmp, tmp};
if(l == r) return ;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
void modify(int u, int x, int v){
if(tr[u].l == tr[u].r){
w[x] = v;
tr[u] = {tr[u].l, tr[u].r, w[x], w[x], w[x], 1};
}else{
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}
int query(int u, int x){ //这个函数很重要Qwq 这个x是会动态变化的， 并不是不变的emm
if(tr[u].l == tr[u].r || tr[u].tmax == tr[u].sum || tr[u].tmax == 0) return tr[u].tmax;
if(x <= tr[u << 1].r){ //在左边
if(x >= tr[u << 1].r - tr[u << 1].rmax + 1) return query(u << 1, x) + query(u << 1 | 1, tr[u << 1 | 1].l);
else return query(u << 1, x);
}
if(x >= tr[u << 1 | 1].l){ //在右边
if(x <= tr[u << 1 | 1].lmax + tr[u << 1 | 1].l - 1) return query(u << 1 | 1, x) + query(u << 1, tr[u << 1].r);
else return query(u << 1 | 1, x);
}
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; ++ i) w[i] = 1;
build(1, 1, n);
while(m --){
char opt; int x;
scanf(" %c", &opt);
if(opt == 'D'){
scanf("%d", &x);
modify(1, x, 0);
distory.push(x);
}else if(opt == 'R'){
x = distory.top();
distory.pop();
modify(1, x, 1);
}else{
scanf("%d", &x);
printf("%d\n", query(1, x));
}
}
return 0;
}
LCIS
题意： 求连续最长上升子序列。 注意query的时候不能简单相加， 例如：1 2 5 8 1 2 3 4，查询1->7的区间时，左边的tlics是4，右边的是3，但是答案并不是简单的4 + 3. 所以返回结构体方便书写。
注意ans结构体要赋予l,r的值！
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100010;
int n,m,t,w[2 * N];
struct node{
int l, r, llcis, rlcis, tlcis, sz;
}tr[N << 2];
void pushup(node& rt, node& ls, node& rs){
rt.llcis = ls.llcis, rt.rlcis = rs.rlcis, rt.tlcis = max(ls.tlcis, rs.tlcis), rt.sz = ls.sz + rs.sz;
if(w[ls.r] < w[rs.l]){
if(ls.tlcis == ls.sz) rt.llcis += rs.llcis;
if(rs.tlcis == rs.sz) rt.rlcis += ls.rlcis;
rt.tlcis = max(rt.tlcis, ls.rlcis + rs.llcis);
}
}
void pushup(int u){
node& rt = tr[u], &ls = tr[u << 1], &rs = tr[u << 1 | 1];
pushup(rt, ls, rs);
}
void build(int u, int l, int r){
tr[u] = {l, r, 1, 1, 1, 1};
if(l == r) return ;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void modify(int u, int x, int v){
if(tr[u].l == tr[u].r) w[x] = v;
else{
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}
void show(node x){
printf("l = %d r = %d tlcis = %d\n", x.l, x.r, x.tlcis);
}
node query(int u, int l, int r){
if(tr[u].l >= l && tr[u].r <= r) return tr[u];
int mid = tr[u].l + tr[u].r >> 1;
if(r <= mid) return query(u << 1, l, r);
if(l > mid) return query(u << 1 | 1, l, r);
else{
node n1, n2, ans;
ans.l = tr[u].l, ans.r = tr[u].r;
n1 = query(u << 1, l, r);
n2 = query(u << 1 | 1, l, r);
pushup(ans, n1, n2);
return ans;
}
}
void solve(){
cin >> n >> m;
for(int i = 1; i <= n; ++ i) scanf("%d", &w[i]);
build(1, 1, n);
while(m --){
char op[20];
int x, y;
scanf(" %s%d%d", op, &x, &y); x ++;
if(op[0] == 'Q') y ++, printf("%d\n", query(1, x, y).tlcis);
else modify(1, x, y);
}
}
int main(){
cin >> t;
while(t --) solve();
return 0;
}
Can you answer these queries III
区间最大连续子段和， 注意query返回node节点。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 500010, inf = 1e9 + 7;
int n,m,w[N];
struct node{
int l,r,lmax,rmax,tmax,sum;
}tr[N << 2];
void pushup(node& root, node& ls, node& rs){
root.sum = ls.sum + rs.sum;
root.lmax = max(ls.lmax, ls.sum + rs.lmax);
root.rmax = max(rs.rmax, rs.sum + ls.rmax);
root.tmax = max(max(ls.tmax, rs.tmax), ls.rmax + rs.lmax);
}
void pushup(int u){
node& root = tr[u], &ls = tr[u << 1], &rs = tr[u << 1 | 1];
pushup(root, ls, rs);
}
void build(int u, int l, int r){
tr[u] = {l, r, w[l], w[l], w[l], w[l]};
if(l == r) return ;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void modify(int u, int x, int v){
if(tr[u].l == tr[u].r) tr[u] = {x, x, v, v, v, v};
else{
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}
//node query(int u, int l, int r){ //这样也可以
// if(tr[u].l >= l && tr[u].r <= r) return tr[u];
// int mid = tr[u].l + tr[u].r >> 1;
// if(r <= mid) return query(u << 1, l, r);
// else if(l > mid) return query(u << 1 | 1, l, r);
// else{
// node n1, n2, res;
// n1 = query(u << 1, l, r);
// n2 = query(u << 1 | 1, l, r);
// pushup(res, n1, n2);
// return res;
// }
//}
node query(int u, int l, int r){
if(tr[u].l >= l && tr[u].r <= r) return tr[u];
int mid = tr[u].l + tr[u].r >> 1;
node n1 = {0,0,-inf,-inf,-inf,0}, n2 = {0,0,-inf,-inf,-inf,0}, res;
if(l <= mid) n1 = query(u << 1, l, r);
if(r > mid) n2 = query(u << 1 | 1, l, r);
pushup(res, n1, n2);
return res;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; ++ i) scanf("%d", &w[i]);
build(1, 1, n);
while(m --){
int opt, x, y;
scanf("%d%d%d",&opt,&x,&y);
if(opt == 1){
if(x > y) swap(x, y);
printf("%d\n", query(1,x,y).tmax);
}
else modify(1,x,y);
}
return 0;
}
Hotel---poj3667/洛谷
题意：题意：酒店有n个房间，现有m个团队，每个团队需要连续 d 个房间，现在有两个操作，1：需要 d 个房间，2：从 x 开始连续 d 个房间退房；
当是1的时候，需要d个房间时， 我们尽可能的找到最靠左的房间给客人，输出最左边房间的编号。
线段树区间合并+区间修改。
维护当前区间的连续空床数。
注意query的时候，分成三类：
A. 左边区间连续空床数>=len， 递归往左边查询；
B. 中间区间连续空床数>=len, 答案就是左边区间的坐标（因为要下标最小， 所以直接tr[u << 1].r - tr[u << 1].rsum + 1;
C. 以上不满足，往右边查询。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 50010;
int n,m;
struct node{
int l, r, lsum, rsum, tsum, sz, lazy;
}tr[N];
void pushup(int u){
node& rt = tr[u], &ls = tr[u << 1], &rs = tr[u << 1 | 1];
rt.lsum = ls.lsum, rt.sz = ls.sz + rs.sz, rt.rsum = rs.rsum;
if(ls.tsum == ls.sz) rt.lsum += rs.lsum;
if(rs.tsum == rs.sz) rt.rsum += ls.rsum;
rt.tsum = max(max(ls.tsum, rs.tsum), ls.rsum + rs.lsum);
}
void build(int u, int l, int r){
tr[u] = {l, r, 1, 1, 1, 1, 0};
if(l == r) return ;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void pushdown(int u){
node& rt = tr[u], &ls = tr[u << 1], &rs = tr[u << 1 | 1];
if(rt.lazy == 0) return ;
if(rt.lazy == 1){ // 要住人, 全满
ls.lazy = rs.lazy = 1;
ls.lsum = ls.rsum = ls.tsum = 0;
rs.lsum = rs.rsum = rs.tsum = 0;
}else{ // 要退房， 全空
ls.lazy = rs.lazy = 2;
ls.lsum = ls.rsum = ls.tsum = ls.sz;
rs.lsum = rs.rsum = rs.tsum = rs.sz;
}
rt.lazy = 0;
}
void update(int u, int l, int r, int v){
if(tr[u].l >= l && tr[u].r <= r){
if(v == 1) tr[u].lsum = tr[u].rsum = tr[u].tsum = 0; //要入住
else tr[u].lsum = tr[u].rsum = tr[u].tsum = tr[u].sz; //要退房
tr[u].lazy = v;
}else{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) update(u << 1, l, r, v);
if(r > mid) update(u << 1 | 1, l, r, v);
pushup(u);
}
}
int query(int u, int l, int r, int len){
pushdown(u);
if(tr[u].l == tr[u].r) return tr[u].l;
int mid = tr[u].l + tr[u].r >> 1;
if(tr[u << 1].tsum >= len) return query(u << 1, l, r, len);
if(tr[u << 1].rsum + tr[u << 1 | 1].lsum >= len) return tr[u << 1].r - tr[u << 1].rsum + 1;
return query(u << 1 | 1, l, r, len);
}
int main(){
cin >> n >> m;
build(1, 1, n);
while(m --){
int opt, x, y;
//printf("re: %d\n", tr[1].tsum);
scanf("%d%d",&opt,&x);
if(opt == 1){
if(tr[1].tsum >= x){
int tmp = query(1, 1, n, x);
printf("%d\n", tmp);
update(1, tmp, tmp + x - 1, 1);
}else puts("0");
}else{
scanf("%d",&y);
update(1, x, x + y - 1, 2);
}
}
return 0;
}线段树求LIS(权值线段树维护dp的最大值)
896. 最长上升子序列 II
tips:注意要求严格单调增， query函数注意。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100010;
int n, idx, mx, a[N], ans = 1;
struct node{
int l, r, maxx;
}tr[N << 2];
vector<int> nums;
int pushup(int u){ tr[u].maxx = max(tr[tr[u].l].maxx, tr[tr[u].r].maxx);}
int build(int l, int r){
int p = ++ idx;
if(l == r) return p;
int mid = l + r >> 1;
tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
return p;
}
void update(int u, int l, int r, int p, int x){
if(l == r) tr[u].maxx = max(tr[u].maxx, x);
else{
int mid = l + r >> 1;
if(p <= mid) update(tr[u].l, l, mid, p, x);
else update(tr[u].r, mid + 1, r, p, x);
pushup(u);
}
}
int query(int u, int l, int r, int p){
if(p > r) return tr[u].maxx;
if(l == r) return l == p ? 0 : tr[u].maxx;
int mid = l + r >> 1;
int ans = query(tr[u].l, l, mid, p);
if(p > mid) ans = max(ans, query(tr[u].r, mid + 1, r, p));
return ans;
}
int get(int x){ return lower_bound(nums.begin(), nums.end(), x) - nums.begin();}
int main(){
cin >> n;
for(int i = 1; i <= n; ++ i){
scanf("%d", &a[i]);
nums.push_back(a[i]);
}
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
mx = nums.size() - 1;
build(0, mx);
for(int i = 1; i <= n; ++ i){
int now = query(1, 0, mx, get(a[i])) + 1;
ans = max(ans, now);
update(1, 0, mx, get(a[i]), now);
}
cout << ans;
return 0;
}LIS
树状数组版：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100010;
int n,m,tr[N],ans,dp[N];
int lowbit(int x){ return x & (-x);}
int ask(int x){ int res = 0; for(int i = x; i >= 1; i -= lowbit(i)) res = max(res, tr[i]) ; return res; }
void add(int x, int v){ for(int i = x; i <= n; i += lowbit(i)) tr[i] = max(tr[i], v);}
int main(){
cin >> n;
for(int i = 1; i <= n; ++ i){
int x;
scanf("%d", &x);
dp[i] = ask(x - 1) + 1;
add(x, dp[i]);
}
for(int i = 1; i <= n; ++ i) ans = max(ans, dp[i]);
cout << ans;
return 0;
}F Fundraising 【离散化树状数组维护二维带权最长上升子序列】
tips:也可以用离散化权值线段树。
这个题是友好城市 的扩展版，不但数据范围加强，而且带权、不能重叠、需要离散化处理。
思路： 先按照某一个维度排序，这样就可以忽略某一维度的信息了（升序排序，一定可以保证这一维度数据上升）， 然后对于两个维度都相同的点，将他们的权值合并； 对于第一维度相同但第二维度不同的点，按照第二维度从大到小排序（这样可以保证第一维度相同的点不会影响答案， 可以画图看看正确性）。然后用树状数组维护即可。
树状数组版：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100010;
int n,m,mx;
ll w[N],tr[N],ans;
vector<ll> nums;
struct node{
int x, y;
ll w;
}a[N];
int cmp(node n1, node n2){ return n1.x == n2.x ? n1.y > n2.y : n1.x < n2.x;}
int lowbit(int x){ return x & (-x);}
ll ask(int x){
ll res = 0;
for(int i = x - 1; i >= 1; i -= lowbit(i)) res = max(res, tr[i]); //因为要求严格单调，从前一个位置开始查
return res;
}
int add(int x, ll c){for(int i = x; i <= mx; i += lowbit(i)) tr[i] = max(tr[i], c);}
int get(int x){ return lower_bound(nums.begin(), nums.end(), x) - nums.begin();}
int main(){
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ){
scanf("%d%d%lld",&a[i].x, &a[i].y, &a[i].w);
nums.push_back(a[i].y); //离散化第二维度即可， 第一维度是排序关键字
}
sort(a + 1, a + 1 + n, cmp);
nums.push_back(-1); //为了让下标从1开始
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
mx = nums.size();
for(int i = 1; i <= n; ++ i){
if(i < n && a[i].x == a[i + 1].x && a[i].y == a[i + 1].y){ //对于两个维度都相同的点，进行合并
a[i + 1].w += a[i].w;
continue;
}
int id = get(a[i].y);
ll tmp = ask(id) + a[i].w;
ans = max(ans, tmp);
add(id, tmp);
}
cout << ans;
return 0;
}权值线段树版：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100010;
int n,m,mx,idx;
ll ans;
vector<ll> nums;
struct node{
int x, y;
ll w;
}a[N];
int cmp(node n1, node n2){ return n1.x == n2.x ? n1.y > n2.y : n1.x < n2.x;}
struct Tr{
int l, r;
ll maxx;
}tr[N << 2];
void pushup(int u){tr[u].maxx = max(tr[tr[u].l].maxx, tr[tr[u].r].maxx);}
int build(int l, int r){
int p = ++ idx;
if(l == r) return p;
int mid = l + r >> 1;
tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
return p;
}
void modify(int u, int l, int r, int p, ll v){
if(l == r) tr[u].maxx = max(tr[u].maxx, v);
else{
int mid = l + r >> 1;
if(p <= mid) modify(tr[u].l, l, mid, p, v);
else modify(tr[u].r, mid + 1, r, p, v);
pushup(u);
}
}
ll query(int u, int l, int r, int p){
if(p > r) return tr[u].maxx;
if(p == l && p == r) return 0;
int mid = l + r >> 1;
ll ans = query(tr[u].l, l, mid, p);
if(p > mid) ans = max(ans, query(tr[u].r, mid + 1, r, p));
return ans;
}
int get(int x){ return lower_bound(nums.begin(), nums.end(), x) - nums.begin();}
int main(){
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ){
scanf("%d%d%lld",&a[i].x, &a[i].y, &a[i].w);
nums.push_back(a[i].y); //离散化第二维度即可， 第一维度是排序关键字
}
sort(a + 1, a + 1 + n, cmp);
nums.push_back(-1); //为了让下标从1开始
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
mx = nums.size();
build(1, mx);
for(int i = 1; i <= n; ++ i){
if(i < n && a[i].x == a[i + 1].x && a[i].y == a[i + 1].y){ //对于两个维度都相同的点，进行合并
a[i + 1].w += a[i].w;
continue;
}
int id = get(a[i].y);
ll tmp = query(1, 1, mx, id) + a[i].w;
ans = max(ans, tmp);
modify(1, 1, mx, id, tmp);
}
cout << ans;
return 0;
}POJ - 2777 Count Color 【线段树维护区间不同数的个数】
题意：
给出一个序列，一开始都是数字1代表第一种颜色，最多有30种颜色，现在有两种操作：
1 x y col将区间[x,y]的气球都变成颜色col
2 x y 查询区间内不同颜色的气球个数
tips:这个题颜色个数很小，只有30个，可以直接二进制状压表示颜色即可。
将一个区间全部变成某个颜色时，pushdown时直接让左右孩子的颜色等于lazy的颜色即可。
注意query函数并不是简单的相加（可以左右区间的颜色相同）
注意了解:
__builtin_popcount()用于计算一个 32 位无符号整数有多少个位为1
#include<iostream>
#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;
const int N = 100010;
struct node{
int l, r,color, lazy;
}tr[N << 2];
int n,m,k;
void pushup(int u){ tr[u].color = tr[u << 1].color | tr[u << 1 | 1].color; }
void pushdown(int u){
if(tr[u].lazy){
tr[u << 1].lazy = tr[u << 1 | 1].lazy = tr[u].lazy;
tr[u << 1].color = tr[u << 1 | 1].color = tr[u].lazy;
tr[u].lazy = 0;
}
}
void build(int u, int l, int r){
tr[u] = {l, r, 1, 0};
if(l == r) return ;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void update(int u, int l, int r, int v){
if(tr[u].l >= l && tr[u].r <= r) tr[u].lazy = tr[u].color = 1 << (v - 1);
else{
int mid = tr[u].l + tr[u].r >> 1;
pushdown(u);
if(l <= mid) update(u << 1, l, r, v);
if(r > mid) update(u << 1 | 1, l, r, v);
pushup(u);
}
}
node query(int u, int l, int r){
if(tr[u].l >= l && tr[u].r <= r) {
//printf("--l = %d r = %d co = %d\n", tr[u].l, tr[u].r, tr[u].color);
return tr[u];
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
node n1, n2, res;
if(r <= mid) return query(u << 1, l, r);
if(l > mid) return query(u << 1 | 1, l, r);
else{
n1 = query(u << 1, l, r);
n2 = query(u << 1 | 1, l, r);
res.color = n1.color | n2.color;
return res;
}
}
int main(){
cin >> n >> k >> m;
build(1, 1, n);
while (m -- ){
char op; int x, y, z;
scanf(" %c%d%d",&op,&x,&y);
if(x > y) swap(x, y);
if(op == 'C'){
scanf("%d", &z);
update(1, x, y, z);
//printf("--%d\n", query(1, x, y));
}else printf("%d\n", __builtin_popcount(query(1, x, y).color));
}
return 0;
}Codeforces Beta Round #43 D. Parking Lot
题意： 有一条长度为L的街道,有N个操作,操作有两种,（1）"1 a"，表示有一辆长度为a的车开进来想找停车位,停车位必须满足与它前面的车距离至少为b,与后面的车距离至少为f.如果能找到这样的停车位,输出这辆车的起始位置(且这个位置最小),否则输出-1。（2）"2 a"，表示第a个事件里进来停车的那辆车开出去了。
tips：当一辆车停进来的时候，要满足前后的间距要求；但是这辆车停下，下一辆车停好后，可能不满足前一辆车的间距要求了！ 例如b = 1, f = 2，前一辆车所在区间是[3,6],下一辆车可以从7开始停车（只需要满足7 - b >= 6即可）。
注意最开始的位置不需要满足与后面间隔是b的条件， 而最后一辆车也不需要满足和前面间隔是f的条件（这一点可以通过建立n + b + f长度的线段树来解决）。询问的时候询问len + b + f, 而修改的时候只修改len(b,f只是间隔)
注意query函数， 其他就是和hotel一样的写法。
#include<bits/stdc++.h>
#define PII pair<int, int>
#define x first
#define y second
#define ll long long
using namespace std;
const int N = 100210;
int n,m,b,f,car;
PII park[N];
struct node{
int l, r, lsum, rsum, tsum, sz, lazy;
}tr[N << 2];
void pushup(int u){
node& rt = tr[u], &ls = tr[u << 1], &rs = tr[u << 1 | 1];
rt.lsum = ls.lsum, rt.rsum = rs.rsum, rt.sz = ls.sz + rs.sz;
if(ls.tsum == ls.sz) rt.lsum += rs.lsum;
if(rs.tsum == rs.sz) rt.rsum += ls.rsum;
rt.tsum = max(max(ls.tsum, rs.tsum), ls.rsum + rs.lsum);
}
void build(int u, int l, int r){
tr[u] = {l, r, 1, 1, 1, 1, 0};
if(l == r) return ;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void pushdown(int u){
node& rt = tr[u], &ls = tr[u << 1], &rs = tr[u << 1 | 1];
if(rt.lazy){
ls.lazy = rt.lazy, rs.lazy = rt.lazy;
if(rt.lazy == 1){ //parking
ls.lsum = ls.rsum = ls.tsum = 0;
rs.lsum = rs.rsum = rs.tsum = 0;
}else{ //leaving
ls.lsum = ls.rsum = ls.tsum = ls.sz;
rs.lsum = rs.rsum = rs.tsum = rs.sz;
}
rt.lazy = 0;
}
}
void update(int u, int l, int r, int v){
if(tr[u].l >= l && tr[u].r <= r){
tr[u].lazy = v;
if(v == 1) tr[u].lsum = tr[u].rsum = tr[u].tsum = 0;
else tr[u].lsum = tr[u].rsum = tr[u].tsum = tr[u].sz;
}else{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) update(u << 1, l, r, v);
if(r > mid) update(u << 1 | 1, l, r, v);
pushup(u);
}
}
int query(int u, int l, int r, int len){
pushdown(u);
if(tr[u].l == 1 && tr[u].lsum + b >= len) return 1; //最头上不需要管b的间隔
if(tr[u].l == tr[u].r) return tr[u].l;
int mid = tr[u].l + tr[u].r >> 1;
if(tr[u << 1].tsum >= len) return query(u << 1, l, r, len);
if(tr[u << 1].rsum + tr[u << 1 | 1].lsum >= len) return tr[u << 1].r - tr[u << 1].rsum + 1;
return query(u << 1 | 1, l, r, len);
}
int main(){
cin >> n >> b >> f;
build(1, 1, n + b + f);
cin >> m;
for(int z = 1; z <= m; ++ z){
int opt, x;
scanf("%d%d",&opt,&x);
if(opt == 1){
if(tr[1].tsum < x + b + f) puts("-1");
else{
int tmp = query(1, 1, n + b + f, x + b + f);
if(tmp != 1) tmp += b;
if(tmp + x - 1 > n){
puts("-1");
continue ;
}
park[z] = {tmp - 1, tmp + x};
printf("%d\n", tmp - 1);
update(1, tmp, tmp + x - 1, 1);
}
}else{
PII now = park[x];
update(1, now.x, now.y, 2);
}
}
return 0;
}hdu3397 Sequence operation 【毒瘤】
题意： 有N个为0或为1的数，有M个操作，操作有5种类型。（1）“0 a b”，表示将区间[a,b]范围内的数全部置0。（2）“1 a b”，表示将区间[a,b]内的数全部置1。（3）"2 a b"，表示将区间[a,b]内的数0变成1，1变成0。（4）"3ab"，表示查询[a,b]范围内1的数。（5）"4 a b"，表示查询[a,b]范围内最长的连续的1。
思路：区间合并的综合应用。
维护左边、右边、总体连续的1、0，1、0的个数等。
注意如果某个点有reverse标记，然后上面下传了lazy,那就把这个reverse去掉（这里非常重要。如果不去，下面那个操作的pushdown可能会因为这里的reverse而超时），因为一定会被全部变成lazy，没有必要翻转了；如果某个点有lazy标记，上面下传了reverese,则先pushdown(ls,rs),把这个子树的lazy标记全部下放（如果孩子的孩子也有lazy，那就继续下放），再reverse,这样可以保证不错（否则lazy和reverse会乱）。
然后就是常规的区间合并。
#include<iostream>
#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;
const int N = 100010;
struct node{
int l, r, sz, sz1, sz0, llen1, llen0, rlen1, rlen0, tlen1, tlen0, lazy, reverse;
}tr[N * 6];
int n,w[N],m,t;
void pushup(node& rt, node& ls, node& rs){
rt.sz = ls.sz + rs.sz, rt.sz1 = ls.sz1 + rs.sz1, rt.sz0 = ls.sz0 + rs.sz0;
rt.llen1 = ls.llen1, rt.llen0 = ls.llen0, rt.rlen1 = rs.rlen1, rt.rlen0 = rs.rlen0;
rt.tlen1 = max(max(ls.tlen1, rs.tlen1), ls.rlen1 + rs.llen1), rt.tlen0 = max(max(ls.tlen0, rs.tlen0), ls.rlen0 + rs.llen0);
if(ls.tlen1 == ls.sz) rt.llen1 += rs.llen1;
if(ls.tlen0 == ls.sz) rt.llen0 += rs.llen0;
if(rs.tlen1 == rs.sz) rt.rlen1 += ls.rlen1;
if(rs.tlen0 == rs.sz) rt.rlen0 += ls.rlen0;
}
void pushup(int u){ pushup(tr[u], tr[u << 1], tr[u << 1 | 1]); }
void build(int u, int l, int r){
tr[u] = {l, r, 1, w[l] == 1, w[l] == 0, w[l] == 1, w[l] == 0, w[l] == 1, w[l] == 0, w[l] == 1, w[l] == 0, -1, 0};
if(l == r) return ;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void Swap(node& rt){ swap(rt.llen0, rt.llen1), swap(rt.rlen1, rt.rlen0), swap(rt.tlen0, rt.tlen1);swap(rt.sz0, rt.sz1);}
void pushdown(int u){
node& rt = tr[u], &ls = tr[u << 1], &rs = tr[u << 1 | 1];
if(rt.l == rt.r) return ;
if(rt.reverse){
pushdown(u << 1); pushdown(u << 1 | 1);
Swap(ls); Swap(rs);
ls.reverse ^= 1, rs.reverse ^= 1;
rt.reverse = 0;
}
if(rt.lazy != -1){
ls.reverse = rs.reverse = 0;
if(rt.lazy == 1){ //全变成1
ls.lazy = rs.lazy = 1;
ls.sz1 = ls.sz, rs.sz1 = rs.sz, ls.sz0 = rs.sz0 = 0;
ls.llen1 = ls.rlen1 = ls.tlen1 = ls.sz;
ls.llen0 = ls.rlen0 = ls.tlen0 = 0;
rs.llen1 = rs.rlen1 = rs.tlen1 = rs.sz;
rs.llen0 = rs.rlen0 = rs.tlen0 = 0;
}else if(rt.lazy == 0){ //全变成0
ls.lazy = rs.lazy = 0;
ls.sz0 = ls.sz, rs.sz0 = rs.sz, ls.sz1 = rs.sz1 = 0;
ls.llen0 = ls.rlen0 = ls.tlen0 = ls.sz;
ls.llen1 = ls.rlen1 = ls.tlen1 = 0;
rs.llen0 = rs.rlen0 = rs.tlen0 = rs.sz;
rs.llen1 = rs.rlen1 = rs.tlen1 = 0;
}
rt.lazy = -1;
}
}
void update(int u, int l, int r, int v){
node& rt = tr[u], &ls = tr[u << 1], &rs = tr[u << 1 | 1];
if(tr[u].l >= l && tr[u].r <= r){
if(v == 1) rt.lazy = 1, rt.reverse = 0, rt.sz1 = rt.sz, rt.sz0 = 0, rt.llen1 = rt.rlen1 = rt.tlen1 = rt.sz, rt.llen0 = rt.rlen0 = rt.tlen0 = 0;
else if(v == 0) rt.lazy = 0, rt.reverse = 0, rt.sz0 = rt.sz, rt.sz1 = 0, rt.llen0 = rt.rlen0 = rt.tlen0 = rt.sz, rt.llen1 = rt.rlen1 = rt.tlen1 = 0;
else{
if(rt.lazy != -1) rt.lazy ^= 1;
rt.reverse ^= 1;
Swap(rt);
}
}else{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) update(u << 1, l, r, v);
if(r > mid) update(u << 1 | 1, l, r, v);
pushup(u);
}
}
node query(int u, int l, int r){
if(tr[u].l >= l && tr[u].r <= r) return tr[u];
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(r <= mid) return query(u << 1, l, r);
else if(l > mid) return query(u << 1 | 1, l, r);
else{
node n1 = query(u << 1, l, r);
node n2 = query(u << 1 | 1, l, r);
node res = {l,r,0,0,0,0,0,0,0,0,0,-1,0}; pushup(res, n1, n2);
return res;
}
}
int main(){
cin >> t;
while(t --){
cin >> n >> m;
for(int i = 1; i <= n; ++ i) scanf("%d",&w[i]);
build(1, 1, n);
while(m --){
int op, x, y;
scanf("%d%d%d",&op,&x,&y); x ++, y ++;
if(op == 0) update(1, x, y, 0);
else if(op == 1) update(1, x, y, 1);
else if(op == 2) update(1, x, y, 2);
else if(op == 3) printf("%d\n", query(1, x, y).sz1);
else{
node n1 = query(1, x, y);
printf("%d\n", n1.tlen1);
}
}
}
return 0;
}
京公网安备 11010502036488号