模板题
#include<cstdio>
#define l(k) (k << 1)
#define r(k) ((k << 1) + 1)
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
struct node
{
ll f, w;
int l, r;
int len() { return r - l + 1; }
int m() { return (l + r) >> 1; }
}tree[MAXN << 2];
void up(int k) { tree[k].w = tree[l(k)].w + tree[r(k)].w; } //这里是=，不是+=。根据题目可以改成max等
void down(int k)
{
ll t = tree[k].f; tree[k].f = 0;
tree[l(k)].f += t; tree[r(k)].f += t;
tree[l(k)].w += t * tree[l(k)].len();
tree[r(k)].w += t * tree[r(k)].len();
}
void build(int k, int l, int r)
{
tree[k].l = l; tree[k].r = r; tree[k].f = 0;//初始化，记得f = 0
if(l == r)
{
scanf("%lld", &tree[k].w);
return;
}
int m = tree[k].m();
build(l(k), l, m);
build(r(k), m + 1, r);
up(k);
}
void add(int k, int x, ll c)
{
if(tree[k].len() == 1)
{
tree[k].w += c;
return;
}
if(tree[k].f) down(k);
int m = tree[k].m();
if(x <= m) add(l(k), x, c);
else add(r(k), x, c);
up(k);
}
void change(int k, int L, int R, ll c)
{
if(L <= tree[k].l && tree[k].r <= R)
{
tree[k].w += tree[k].len() * c;
tree[k].f += c;
return;
}
if(tree[k].f) down(k);
int m = tree[k].m();
if(L <= m) change(l(k), L, R, c);
if(R > m) change(r(k), L, R, c);
up(k);
}
ll sum(int k, int L, int R)
{
if(L <= tree[k].l && tree[k].r <= R) return tree[k].w;
if(tree[k].f) down(k); //注意这句话除了build外每个函数都要打
ll res = 0;
int m = tree[k].m();
if(L <= m) res += sum(l(k), L, R);
if(R > m) res += sum(r(k), L, R);
return res;
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
build(1, 1, n);
while(m--)
{
int p, x, y; ll c;
scanf("%d%d%d", &p, &x, &y);
if(p == 1)
{
scanf("%lld", &c);
change(1, x, y, c);
}
else printf("%lld
", sum(1, x, y));
}
return 0;
}#include<cstdio>
#include<algorithm>
#define l(k) (k << 1)
#define r(k) ((k << 1) + 1)
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
const int MAXN = 200000 + 10;
struct node
{
int l, r, w;
int m() { return (l + r) >> 1; }
}tree[MAXN << 2];
void up(int k) { tree[k].w = max(tree[l(k)].w, tree[r(k)].w); }
void build(int k, int l, int r)
{
tree[k].l = l; tree[k].r = r;
if(l == r)
{
scanf("%d", &tree[k].w);
return;
}
int m = tree[k].m();
build(l(k), l, m);
build(r(k), m + 1, r);
up(k);
}
void change(int k, int x, int q)
{
if(tree[k].l == tree[k].r)
{
tree[k].w = q;
return;
}
int m = tree[k].m();
if(x <= m) change(l(k), x, q);
else change(r(k), x, q);
up(k);
}
int ans(int k, int L, int R)
{
if(L <= tree[k].l && tree[k].r <= R) return tree[k].w;
int m = tree[k].m(), res = 0;
if(L <= m) res = max(res, ans(l(k), L, R));
if(m < R) res = max(res, ans(r(k), L, R));
return res;
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
build(1, 1, n);
while(m--)
{
char s[5]; int x, y;
scanf("%s%d%d", s, &x, &y);
if(s[0] == 'C') change(1, x, y);
else
{
if(x > y) swap(x, y);
printf("%d
", ans(1, x, y));
}
}
return 0;
}#include<bits/stdc++.h>
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 10;
struct tree
{
int l, r, w;
int m() { return (l + r) >> 1; }
}t[MAXN << 2];
int m, p, len;
void read(int& x)
{
int f = 1; x = 0; char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
x *= f;
}
inline void up(int k)
{
t[k].w = max(t[l(k)].w, t[r(k)].w);
}
void bulid(int k, int l, int r)
{
t[k].l = l; t[k].r = r;
if(l == r) return;
int m = t[k].m();
bulid(l(k), l, m);
bulid(r(k), m + 1, r);
up(k);
}
void add(int k, int x, int val)
{
if(t[k].l == t[k].r)
{
t[k].w = val;
return;
}
int m = t[k].m();
if(x <= m) add(l(k), x, val);
else add(r(k), x, val);
up(k);
}
int search(int k, int L, int R)
{
if(L <= t[k].l && t[k].r <= R) return t[k].w;
int m = t[k].m(), res = 0;
if(L <= m) res = max(res, search(l(k), L, R));
if(R > m) res = max(res, search(r(k), L, R));
return res;
}
int main()
{
read(m); read(p);
bulid(1, 1, m);
int a = 0;
REP(i, 0, m)
{
char s[5]; int t;
scanf("%s%d", s, &t);
if(s[0] == 'A') add(1, ++len, (t + a) % p);
else printf("%d
", a = search(1, len - t + 1, len));
}
return 0;
}区间染色问题
因为只有30种颜色，而int是32位，所以可以用一个int来表示状态，相当于状态压缩
同理如果大于30，可以用long long
然后并的时候取或，新的颜色进来的时候记得是1<<tt
然后题目给的l和r要考虑交换
#include<cstdio>
#include<algorithm>
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register i = (a); i <= (b); i++)
using namespace std;
const int MAXN = 1e5 + 10;
struct node
{
int l, r, f, w;
int m() { return (l + r) >> 1; }
}tree[MAXN << 2];
inline void up(int k) { tree[k].w = tree[l(k)].w | tree[r(k)].w; }
inline void down(int k)
{
if(!tree[k].f) return;
int t = tree[k].f; tree[k].f = 0;
tree[l(k)].f = tree[r(k)].f = t;
tree[l(k)].w = tree[r(k)].w = t;
}
void build(int k, int l, int r)
{
tree[k].l = l; tree[k].r = r; tree[k].f = 0; tree[k].w = 2; //第一位是2,不是1！！
if(l == r) return;
int m = tree[k].m();
build(l(k), l, m);
build(r(k), m + 1, r);
up(k);
}
void change(int k, int L, int R, int q)
{
if(L <= tree[k].l && tree[k].r <= R)
{
tree[k].f = tree[k].w = q;
return;
}
down(k);
int m = tree[k].m();
if(L <= m) change(l(k), L, R, q);
if(R > m) change(r(k), L, R, q);
up(k);
}
int ans(int k, int L, int R)
{
if(L <= tree[k].l && tree[k].r <= R) return tree[k].w;
down(k);
int m = tree[k].m();
int res = 0;
if(L <= m) res |= ans(l(k), L, R);
if(m < R) res |= ans(r(k), L, R);
return res;
}
int num(int x) { return !x ? 0 : 1 + num(x & (x - 1)); }
int main()
{
int n, m, t;
while(~scanf("%d%d%d", &n, &t, &m))
{
build(1, 1, n);
while(m--)
{
char s[5]; int x, y;
scanf("%s%d%d", s, &x, &y);
if(x > y) swap(x, y);
if(s[0] == 'C')
{
int tt; scanf("%d", &tt);
change(1, x, y, 1 << tt); //记住是1<<tt，不是tt
}
else printf("%d
", num(ans(1, x, y)));
}
}
return 0;
}区间开方
一开始发现开根号不能合并。然后又觉得单点更新绝对超时。
然后发现一个数开多几次就是1了。这个时候不用继续开了。
所以我们可以同时维护最大值以及和，如果最大值为<=1
就不用更新了。这样就可以快很多。
所以就是单点更新加优化
#include<bits/stdc++.h>
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
struct tree
{
int l, r, num; ll ma, w;
int m() { return (l + r) >> 1; }
}t[MAXN << 2];
int n, m, L, R, op;
void read(int& x)
{
int f = 1; x = 0; char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
x *= f;
}
void readll(ll& x)
{
ll f = 1; x = 0; char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
x *= f;
}
inline void up(int k)
{
t[k].w = t[l(k)].w + t[r(k)].w;
t[k].ma = max(t[l(k)].ma, t[r(k)].ma);
}
void bulid(int k, int l, int r)
{
t[k].l = l; t[k].r = r;
if(l == r) { readll(t[k].w); t[k].ma = t[k].w; return; }
int m = t[k].m();
bulid(l(k), l, m);
bulid(r(k), m + 1, r);
up(k);
}
void change(int k)
{
if(t[k].ma <= 1) return;
if(t[k].l == t[k].r)
{
t[k].w = sqrt(t[k].w);
t[k].ma = sqrt(t[k].ma);
return;
}
int m = t[k].m();
if(L <= m) change(l(k)); if(R > m) change(r(k));
up(k);
}
ll search(int k)
{
if(L <= t[k].l && t[k].r <= R) return t[k].w;
int m = t[k].m(); ll res = 0;
return (L <= m ? search(l(k)) : 0) + (R > m ? search(r(k)) : 0);
}
int main()
{
read(n);
bulid(1, 1, n);
read(m);
while(m--)
{
read(op); read(L); read(R);
if(op == 1) printf("%lld
", search(1));
else change(1);
}
return 0;
}加和乘双重懒标记
这道题细节比较多
这里又两个懒标记，问题是标记的时候怎么合并，然后下放子节点的时候怎么弄
这里有个问题，是先乘后加还是先加后乘
如果先加后乘
那么假设原来本身的值是5， add(加法懒标记)是3， mul = 7（乘法懒标记）且是叶子节点
那么就是 （5 + 3） * 7 = 56
这个时候如果再加一个值，即add++， 那么答案应该是57
那么这个时候懒标记该怎么改？？加法就是+1， 那么乘法呢？？
（5 + （3 + 1）） * ？？？？ = 57
这个时候乘法懒标记会变成小数，显然不行
那么我们看看先乘后加
5 * 7 + 3 = 38
如果乘上2，答案为76
这时显然乘法懒标记乘上2
5 * 14 + ？？？ = 76
这个时候？？？为6
也就是说，只要加法的懒标记也乘上2就可以了
综上所述，先乘后加
#include<bits/stdc++.h>
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#define cal1(a, b) a = (a * b) % MOD
#define cal2(a, b) a = (a + b) % MOD
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
struct tree
{
int l, r;
ll add, mul, w;
int m() { return (l + r) >> 1; }
int len() { return r - l + 1; }
void clean() { add = 0; mul = 1; }
}t[MAXN << 2];
int n, m, L, R, op, MOD;
ll g;
void read(int& x)
{
int f = 1; x = 0; char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
x *= f;
}
void readll(ll& x)
{
ll f = 1; x = 0; char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
x *= f;
}
inline void up(int k) { t[k].w = (t[l(k)].w + t[r(k)].w) % MOD; }
inline void deal(int f, int s)
{
t[s].w = (t[s].w * t[f].mul + t[f].add * t[s].len()) % MOD;
cal1(t[s].mul, t[f].mul);
t[s].add = (t[s].add * t[f].mul + t[f].add) % MOD;
}
inline void down(int k)
{
deal(k, l(k));
deal(k, r(k));
t[k].clean();
}
void bulid(int k, int l, int r)
{
t[k].clean(); //一定要初始化
t[k].l = l; t[k].r = r;
if(l == r)
{
readll(t[k].w);
return;
}
int m = t[k].m();
bulid(l(k), l, m);
bulid(r(k), m + 1, r);
up(k);
}
void change1(int k)
{
if(L <= t[k].l && t[k].r <= R)
{
cal1(t[k].w, g); cal1(t[k].mul, g);
cal1(t[k].add, g); return; //加的懒标记要乘，很关键
}
down(k); int m = t[k].m();
if(L <= m) change1(l(k)); if(R > m) change1(r(k)); up(k);
}
void change2(int k)
{
if(L <= t[k].l && t[k].r <= R)
{
cal2(t[k].w, g * t[k].len());
cal2(t[k].add, g); return;
}
down(k); int m = t[k].m();
if(L <= m) change2(l(k)); if(R > m) change2(r(k)); up(k);
}
ll query(int k)
{
if(L <= t[k].l && t[k].r <= R) return t[k].w;
int m = t[k].m(); down(k);
return (L <= m ? query(l(k)) : 0) + (R > m ? query(r(k)) : 0);
}
int main()
{
read(n); read(m); read(MOD);
bulid(1, 1, n);
while(m--)
{
read(op); read(L); read(R);
if(op == 1) { readll(g); change1(1); }
if(op == 2) { readll(g); change2(1); }
if(op == 3) printf("%lld
", query(1) % MOD);
}
return 0;
}离散化+染色
（1）区间的范围非常大，我们可以离散化，只保留相对大小关系即可。要注意离散化的点之间有没有被染色的地方
离散化之后尤其 要注意空间大小要怎么开，我在这卡了很久。
（2）染色的话就维护颜色，只要子树颜色不一样就设置为-1， 空地也设置为-1（因为空地不加入答案）， 然后询问的时候只要是-1就继续往下，直到有一整个子树都是一个颜色的时候更新答案。注意颜色不能重复，要开一个vis数组
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;
typedef long long ll;
const int MAXN = 2e4 + 10;
struct tree
{
int l, r, color, f;
int m() { return (l + r) >> 1; }
}t[MAXN << 4];
int a[MAXN * 3], x[MAXN], y[MAXN], vis[MAXN * 3];
int n, m, L, R;
inline void read(int& x)
{
int f = 1; x = 0; char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
x *= f;
}
inline void up(int k)
{
if(t[l(k)].color != t[r(k)].color) t[k].color = -1;
else t[k].color = t[l(k)].color;
}
inline void draw(int k, int color) { t[k].f = t[k].color = color; }
inline void down(int k)
{
if(!t[k].f) return;
draw(l(k), t[k].f);
draw(r(k), t[k].f);
t[k].f = 0;
}
void bulid(int k, int l, int r)
{
t[k].l = l; t[k].r = r; t[k].color = -1; t[k].f = 0;
if(l == r) return;
int m = t[k].m();
bulid(l(k), l, m);
bulid(r(k), m + 1, r);
up(k);
}
void add(int k, int color)
{
if(L <= t[k].l && t[k].r <= R)
{
draw(k, color);
return;
}
down(k); int m = t[k].m();
if(L <= m) add(l(k), color); if(R > m) add(r(k), color); up(k);
}
int query(int k)
{
if(t[k].color != -1)
{
if(!vis[t[k].color])
{
vis[t[k].color] = 1;
return 1;
}
else return 0;
}
if(t[k].l == t[k].r) return 0;
int m = t[k].m(); down(k);
return query(l(k)) + query(r(k));
}
void init()
{
sort(a, a + m);
m = unique(a, a + m) - a;
int t = m;
REP(i, 1, t)
if(a[i] - a[i-1] > 1)
a[m++] = a[i] - 1;
sort(a, a + m);
}
int main()
{
int T; read(T);
while(T--)
{
memset(vis, 0, sizeof(vis));
read(n); m = 0;
REP(i, 0, n)
{
read(x[i]); read(y[i]);
a[m++] = x[i]; a[m++] = y[i];
}
init();
bulid(1, 1, m);
REP(i, 0, n)
{
L = lower_bound(a, a + m, x[i]) - a + 1;
R = lower_bound(a, a + m, y[i]) - a + 1;
add(1, i + 1);
}
printf("%d
", query(1));
}
return 0;
}