支持区间修改(加),和区间查询
#include<iostream>
using namespace std;
const int N = 320010;
using i64 = long long;
i64 a[N];
struct Node{
int l,r;
i64 sum,add;
} tr[N * 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.sum += (i64)(left.r - left.l + 1) * root.add,left.add += root.add;
right.sum += (i64)(right.r - right.l + 1) * root.add , right.add += root.add;
root.add = 0;
}
}
void modify(int u , int l , int r , int x){
if(tr[u].l >= l && tr[u].r <= r) {
tr[u].sum += (i64)(tr[u].r - tr[u].l + 1) * x;
tr[u].add += x;
} else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1 , l , r , x);
if(r > mid) modify(u << 1 | 1 , l, r , x);
pushup(u);
}
}
i64 query(int u , int l , int r){
if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
pushdown(u); // 记得传递懒标记
i64 v = 0;
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) v += query(u << 1 , l , r);
if(r > mid) v += query(u << 1 | 1 , l , r);
return v;
}
void build(int u , int l , int r){
if(l == r) tr[u] = { r, r , a[r] , 0};
else {
tr[u] = {l , r}; // 记得更新区间端点
int mid = l + r >> 1;
build(u << 1 , l , mid);
build(u << 1 | 1 , mid + 1 , r);
pushup(u);
}
}
支持区间修改(乘 , 加) , 支持区间查询 (这是洛谷上的 , 似乎数据弱一些)
#include<iostream>
using namespace std;
const int N = 520010;
using i64 = long long;
int mod;
i64 a[N];
struct Node{
int l,r;
i64 sum,add,mul;
} tr[N * 4];
void pushup(int u){
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void eval(Node &a,int mul,int add)
{
a.sum = ((i64)a.sum * mul % mod + (i64)(a.r - a.l + 1) * add % mod) % mod;
a.mul = ((i64)a.mul * mul) % mod;
a.add = (a.add * mul % mod + add) % mod;
}
void pushdown(int u)
{
eval(tr[u << 1],tr[u].mul,tr[u].add);
eval(tr[u << 1 | 1],tr[u].mul,tr[u].add);
tr[u].mul = 1;
tr[u].add = 0;
}
void modify(int u , int l , int r , int x ,int mul){
if(tr[u].l >= l && tr[u].r <= r) {
eval(tr[u] , mul , x);
} else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1 , l , r , x , mul);
if(r > mid) modify(u << 1 | 1 , l, r , x , mul);
pushup(u);
}
}
i64 query(int u , int l , int r){
if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
pushdown(u); // 记得传递懒标记
i64 v = 0;
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) v += query(u << 1 , l , r);
if(r > mid) v += query(u << 1 | 1 , l , r);
return v;
}
void build(int u , int l , int r){
if(l == r) tr[u] = { r, r , a[r] ,0,1};
else {
tr[u] = {l , r};// 记得更新区间端点
tr[u].mul = 1;// 记得在初始化的时候,时刻维护mul为1
int mid = l + r >> 1;
build(u << 1 , l , mid);
build(u << 1 | 1 , mid + 1 , r);
pushup(u);
}
}
int main(){
int n,m;cin >> n >> m >> mod;
for(int i = 1;i <= n;i ++ ) cin >> a[i];
build(1,1,n);
while(m -- ){
int t,l,r;
cin >> t >> l >> r;
if(t == 1) {
int k;cin >> k;
modify(1, l, r, 0 ,k);
} else if(t == 2) {
int k;
cin >> k;
modify(1 , l ,r, k ,1);
} else {
cout << query(1 , l , r) % mod << '\n';
}
}
}
这是acwing上的数据似乎强一点
#include <iostream>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 100010;
struct Tree{
int l,r;
ll sum,mul,add;
};
Tree tr[N << 2];
int n,mod,m;
int w[N];
void pushup(int u)
{
tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % mod;
}
void eval(Tree &a,int mul,int add)
{
a.sum = ((ll)a.sum * mul % mod + (ll)(a.r - a.l + 1) * add % mod) % mod;
a.mul = ((ll)a.mul * mul) % mod;
a.add = (a.add * mul % mod + add) % mod;
}
void pushdown(int u)
{
eval(tr[u << 1],tr[u].mul,tr[u].add);
eval(tr[u << 1 | 1],tr[u].mul,tr[u].add);
tr[u].mul = 1;
tr[u].add = 0;
}
void build(int u,int l,int r)
{
tr[u].l = l;
tr[u].r = r;
tr[u].mul = 1;
tr[u].add = 0;
if(l == r){
tr[u].sum = w[l] % mod;
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 l,int r,int mul,int add)
{
if(l <= tr[u].l && r >= tr[u].r) eval(tr[u],mul,add);
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1,l,r,mul,add);
if(r > mid) modify(u << 1 | 1,l,r,mul,add);
pushup(u);
}
}
ll query(int u,int l,int r)
{
if(l <= tr[u].l && r >= tr[u].r) return tr[u].sum;
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
{
ll left = query(u << 1,l,r);
ll right = query(u << 1 | 1,l,r);
ll res = (left + right) % mod;
return res;
}
}
int main(){
ios :: sync_with_stdio(false);
cin.tie(0);
cin >> n >> mod;
for(int i=1;i<=n;i++) cin >> w[i];
build(1,1,n);
cin >> m;
while(m--)
{
int op,l,r;
cin >> op >> l >> r;
if(op == 1)
{
int c;
cin >> c;
modify(1,l,r,c,0);
}
else if(op == 2)
{
int c;
cin >> c;
modify(1,l,r,1,c);
}
else
{
cout << query(1,l,r) << endl;
}
}
return 0;
}
快读
inline int read() {
int x = 0, fh = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar() ) if (ch == '-') fh = -1;
for (; isdigit(ch); ch = getchar() ) x = (x<<1) + (x<<3) + (ch ^ '0');
return x * fh;
}