注意事项：
1. dfs序上线段树
2. 当是区间覆盖的时候，要记得判定pushdown能不能down，可能会造成错误的初始值覆盖
3. 在想维护哪些信息的时候，只需要考虑在已经这些清晰的情况下，如何递推计算这些信息以及维护标记就行了，不要绕进去
4. 结构体中有多个变量的时候，索引赋值更不容易出错
一个简单的整数问题
// 板子题目，维护区间加法的和
#include
using namespace std;
const int N = 1e5+10;
typedef long long LL;
// 标签在当前节点已经发生作用了，但是还没有对儿孙发生作用
int w[N];
struct node{
int l, r;
LL sum;
LL add;
}tr[4*N];
void pushup(int u){
tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
}
// pusdown主要考虑标签融合，标签向下传递的计算两个方面
void pushdown(node &F, node &L, node &R){
// 标签融合
L.add += F.add;
R.add += F.add;
// 标签向下传递
L.sum = L.sum + (LL)(L.r - L.l + 1) * F.add;
R.sum = R.sum + (LL)(R.r - R.l + 1) * F.add;
// 标签清空
F.add = 0;
}
void pushdown(int u){
pushdown(tr[u], tr[u<<1], tr[u<<1|1]);
}
void build(int u, int l, int r){
if(l == r){
tr[u] = {l, r, w[l], 0};
}
else{
tr[u] = {l, r, 0, 0};
int mid = l + r >> 1;
build(u<<1, l, mid), build(u<<1|1, mid+1, r);
pushup(u);
}
}
// pushdown都是下面的分支里面才有，这样能保证pushdown不越界
void modify(int u, int l, int r, int v){
if(tr[u].l >= l && tr[u].r <= r) {
// 这里修改的时候，标签要发挥作用
tr[u].add += v;
tr[u].sum += (tr[u].r - tr[u].l + 1) * v;
}
else{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u<<1, l, r, v);
if(r > mid) modify(u<<1|1, l, r, v);
pushup(u);
}
}
LL query(int u, int l, int r){
if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
else{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l > mid) return query(u<<1|1, l, r);
else if(r <= mid) return query(u<<1, l, r);
else return query(u<<1, l, r) + query(u<<1|1, l, r);
}
}
int main(){
int n, m;
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
build(1, 1, n);
while(m--){
char op[2]; int l, r, v;
scanf("%s", op);
if(op[0] == 'Q') scanf("%d %d", &l, &r), printf("%lld\n", query(1, l, r));
else scanf("%d %d %d", &l, &r, &v), modify(1, l, r, v);
}
return 0;
}
市长海报
题目：给定n个区间l-r，依次覆盖，问露出来的有多少个
存在的问题
1. 区间覆盖问题要离散的话时候可能会先问题，需要在离散化的时候加入l+1,r+1,这样才能正确区分
2. 该问题前面都是区间修改，后面都是单点查询，所以他就不需要pushup()，
直接在最后进行暴力的单点查询就可以了，而且也不需要维护区间的信息，只要维护好单点的信息就可以了
3. 如果是不需要离散化的区间覆盖呢，那么可以这么转化[l, l]代表[l, l+1]的颜色，那么覆盖[l, r],其实就是覆盖[l, r-1]
#include
using namespace std;
typedef long long LL;
typedef pair PII;
const int N = 4e4+10;
vector pos;
PII seg[N];
// 标签在当前节点已经发生作用了，但是还没有对儿孙发生作用
int w[N];
struct node{
int l, r;
int type;
int label;
}tr[4*N];
void pushdown(node &F, node &L, node &R){
// 标签融合
if(F.label == 0) return ;
L.label = F.label;
R.label = F.label;
// 标签向下传递
L.type = F.label;
R.type = F.label;
// 标签清空
F.label = 0;
}
void pushdown(int u){
pushdown(tr[u], tr[u<<1], tr[u<<1|1]);
}
void build(int u, int l, int r){
if(l == r){
tr[u] = {l, r, 0, 0};
}
else{
tr[u] = {l, r, 0, 0};
int mid = l + r >> 1;
build(u<<1, l, mid), build(u<<1|1, mid+1, r);
}
}
void modify(int u, int l, int r, int v){
if(tr[u].l >= l && tr[u].r <= r) {
tr[u].label = v;
tr[u].type = v;
}
else{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u<<1, l, r, v);
if(r > mid) modify(u<<1|1, l, r, v);
}
}
int query(int u, int l, int r){
if(tr[u].l >= l && tr[u].r <= r) return tr[u].type;
else{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l > mid) return query(u<<1|1, l, r);
else if(r <= mid) return query(u<<1, l, r);
else return query(u<<1, l, r) + query(u<<1|1, l, r);
}
}
int get(int x){
int l = 0, r = pos.size()-1;
while(l < r){
int mid = l + r + 1>> 1;
if(pos[mid] <= x) l = mid;
else r = mid - 1;
}
return l + 1;
}
int main(){
int T;
cin >> T;
while(T--){
int n; scanf("%d", &n);
pos.clear();
for(int i = 1; i <= n; i++){
int l, r; scanf("%d %d", &l, &r);
seg[i] = {l, r};
pos.push_back(l), pos.push_back(r);
pos.push_back(l+1), pos.push_back(r+1);
}
sort(pos.begin(), pos.end());
pos.erase(unique(pos.begin(), pos.end()), pos.end());
build(1, 1, pos.size());
for(int i = 1; i <= n; i ++){
int l = get(seg[i].first), r = get(seg[i].second);
modify(1, l, r, i);
}
// cout << 1 << endl;
set S;
S.insert(0);
for(int i = 0; i < pos.size(); i++){
int x = get(pos[i]);
// cout << query(1, x, x ) << endl;
S.insert(query(1, x, x));
}
printf("%d\n", S.size()-1);
}
return 0;
}
你能回答这些问题吗
题目链接：https://www.acwing.com/problem/content/description/4347/
问题：
1.一道带暴力成分的线段树
2.n的和最多是1e6个，数据保证单组测试数据中ei的和不会超过2^63,发现2^63次方开个七八次根号就是1了，所以可以不打标记，
直接暴力修改到叶子，然后加一个剪枝就可以了，具体看代码
3. 时间复杂度，每个叶子最多被修改6，7次，按7次算的话，包含某个叶子权值的线段树节点，就是从这个叶子，不断地向上找父亲，
大概也就20个左右，这些就是将一个叶子的权值变成1最多要修改的次数7*20，最后再乘上叶子的总个数，也就n的和，是小于2e8
#include
using namespace std;
typedef long long LL;
const int N = 1e5+10;
LL w[N];
struct node{
int l, r;
LL sum;
}tr[4*N];
void pushup(int u){
tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
}
void build(int u, int l, int r){
if(l == r){
tr[u] = {l, r, w[l]};
}
else{
tr[u] = {l, r, 0};
int mid = l + r >> 1;
build(u<<1, l, mid), build(u<<1|1, mid+1, r);
pushup(u);
}
}
void modify(int u, int l, int r){
// 如果区间长度等于区间和的话，说明该区间都是1了，就不用递归开根号了
if(tr[u].r - tr[u].l + 1 == tr[u].sum) return ;
// 递归到叶子，直接对叶子修改
if(tr[u].l >= l && tr[u].r <= r && tr[u].l == tr[u].r) {
tr[u].sum = sqrt(tr[u].sum);
}
else{
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u<<1, l, r);
if(r > mid) modify(u<<1|1, l, r);
pushup(u);
}
}
LL 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].l + tr[u].r >> 1;
if(l > mid) return query(u<<1|1, l, r);
else if(r <= mid) return query(u<<1, l, r);
else return query(u<<1, l, r) + query(u<<1|1, l, r);
}
}
int main(){
int C = 0, n;
while(cin >> n){
C++;
printf("Case #%d:\n", C);
for(int i = 1; i <= n; i++) scanf("%lld", &w[i]);
build(1, 1, n);
int m; scanf("%d", &m);
while(m --){
int op, l, r; scanf("%d %d %d", &op, &l, &r);
if(l > r) swap(l, r);
if(op == 0){
modify(1, l, r);
}
else if(op == 1){
printf("%lld\n", query(1, l, r));
}
}
puts("");
}
return 0;
}
地道战
问题：只有01两种元素的数组，动态单点修改，询问包含某个节点的最大连续1的长度
1.维护区间左端最大值，右端最大值，和整体的最大值,pushdown其实是比较好实现的
2.区间查询感觉比较困难，
为啥那么写查询是O(logn)的，而不会退化到O(n)，每次递归的时候只会走一条分支，否则直接返回答案，所以
是log(n)（一共只有log层吧）
另一个就是跨区间的时候，可以直接返回答案，感觉比较难想
#include
using namespace std;
typedef long long LL;
const int N = 50010;
struct node{
int l, r;
int lmax, rmax, maxn;
}tr[4*N];
void pushup(int u){
node & F = tr[u], L = tr[u<<1], R = tr[u<<1|1];
F.maxn = max({L.maxn, R.maxn, L.rmax + R.lmax});
F.lmax = L.lmax;
F.rmax = R.rmax;
if(L.maxn == L.r - L.l + 1) F.lmax = max(F.lmax, L.maxn + R.lmax);
if(R.maxn == R.r - R.l + 1) F.rmax = max(F.rmax, R.maxn + L.rmax);
}
void build(int u, int l, int r){
if(l == r){
tr[u] = {l, r, 1, 1, 1};
}
else{
tr[u] = {l, r, 1, 1, 1};
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 == x && tr[u].r == x){
tr[u].lmax = tr[u].rmax = tr[u].maxn = 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);
}
}
int query(int u, int x){
if(tr[u].maxn == (tr[u].r - tr[u].l + 1) || tr[u].l == tr[u].r) return tr[u].maxn;
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid){
if(mid - tr[u<<1].rmax + 1<= x) return tr[u<<1].rmax + tr[u<<1|1].lmax;
else return query(u<<1, x);
}
else{
if(mid + 1 + tr[u<<1|1].lmax - 1 >= x) return tr[u<<1].rmax + tr[u<<1|1].lmax;
else return query(u<<1|1, x);
}
}
int main(){
int n, m;
while(cin >> n >> m){
build(1, 1, n);
stack stk;
while(m--){
char op[2]; int x;
scanf("%s", op);
if(op[0] == 'D'){
scanf("%d", &x);
stk.push(x);
modify(1, x, 0);
}
else if(op[0] == 'Q'){
scanf("%d", &x);
printf("%d\n", query(1, x));
}
else{
if(stk.size() == 0) continue;
int top = stk.top(); stk.pop();
modify(1, top, 1);
}
}
}
return 0;
}
花瓶与鲜花
一道线段树上的二分，之前也写过一道线段树二分，但是这道和之前的感觉不太一样
之前那个直接query那里二分就可以了，这道题query部分还是正常的，又单独写了一个二分
另外一个关键点是，如何二分x之后的第一个和最后一个，以及如何判断是否不可能
首先可以query出来x之前有多少个空位，这样的话x及其之后第一个空位就是前面+1了，最后一个就算前面+y了
但是如何判断不可能呢，最后一个的计算，我们直接和tr[1]取个min这样的话，算出来的最多也就是最后一个
前面的边界的话，我们不管，这样如果有解的话，他就能算出来一个解，没有解的话他就自动二分道最后一个值了
例外需要注意的是二分里面不能继续缩短范围，不然的话，上面对l的计算可能就不正确了
#include
using namespace std;
typedef long long LL;
const int N = 5e4+10;
struct node{
int l, r;
int sum;
int add;
}tr[4*N];
void pushup(int u){
tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
}
void pushdown(node &F, node &L, node &R){
if(F.add == -1) return ;
// 标签融合
L.add = F.add;
R.add = F.add;
// 标签向下传递
L.sum = (L.r - L.l + 1) * F.add;
R.sum = (R.r - R.l + 1) * F.add;
// 标签清空
F.add = -1;
}
void pushdown(int u){
pushdown(tr[u], tr[u<<1], tr[u<<1|1]);
}
void build(int u, int l, int r){
if(l == r){
tr[u] = {l, r, 1, -1};
}
else{
tr[u] = {l, r, r - l + 1, -1};
int mid = l + r >> 1;
build(u<<1, l, mid), build(u<<1|1, mid+1, r);
}
}
void modify(int u, int l, int r, int v){
if(tr[u].l >= l && tr[u].r <= r) {
tr[u].add = v;
tr[u].sum = v * (tr[u].r - tr[u].l + 1);
}
else{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u<<1, l, r, v);
if(r > mid) modify(u<<1|1, l, r, v);
pushup(u);
}
}
int query(int u, int l, int r){
if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
else{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l > mid) return query(u<<1|1, l, r);
else if(r <= mid) return query(u<<1, l, r);
else return query(u<<1, l, r) + query(u<<1|1, l, r);
}
}
int find(int u, int x){
if(tr[u].l == tr[u].r) return tr[u].l;
pushdown(u);
if(tr[u<<1].sum >= x ) return find(u<<1, x);
else return find(u<<1|1, x - tr[u<<1].sum);
}
int main(){
int T;
scanf("%d", &T);
while(T--){
int n, m; scanf("%d %d", &n, &m);
build(1, 0, n-1);
while(m--){
int op, x, y; scanf("%d %d %d", &op, &x, &y);
if(op == 1){
int lsum = 0;
if(x - 1 >= 0) lsum = query(1, 0, x - 1);
int L = find(1, lsum + 1);
int R = find(1, min(lsum + y, tr[1].sum));
modify(1, L, R, 0);
if( L > R ) printf("Can not put any one.\n");
else printf("%d %d\n", L, R);
}
else if(op == 2){
int pre = query(1, x, y);
modify(1, x, y, 1);
printf("%d\n", y - x + 1 - pre);
}
}
puts("");
}
return 0;
}