别问我为什么是指针
单点修改+区间查询
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
//Mystery_Sky
//线段树模板（单点修改+区间求和）
#define M 500050
#define Mid (l+r)>>1
struct Tree{
Tree *lc, *rc;
int x;
}dizhi[M<<1], *root = &dizhi[0];
int t = 1;
int a[M];
int n, m, k, x, y;
void build(Tree *tree, int l, int r)
{
if(l == r) {
tree->x = a[l];
return;
}
int mid = Mid;
tree->lc = &dizhi[++t];
tree->rc = &dizhi[++t];
build(tree->lc, l, mid);
build(tree->rc, mid+1, r);
tree->x = tree->lc->x + tree->rc->x;
}
void update(Tree *tree, int l, int r, int x, int d)
{
if(l == r) {
tree->x += d;
return;
}
int mid = Mid;
if(x <= mid) update(tree->lc, l, mid, x, d);
else update(tree->rc, mid+1, r, x, d);
tree->x = tree->lc->x + tree->rc->x;
}
int query(Tree *tree, int l, int r, int x, int y)
{
if(x <= l && y >= r) {
return tree->x;
}
int mid = Mid;
int ans = 0;
if(x <= mid) ans += query(tree->lc, l, mid, x, y);
if(y > mid) ans += query(tree->rc, mid+1, r, x, y);
return ans;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
build(root, 1, n);
for(int i = 1; i <= m; i++) {
scanf("%d%d%d", &k, &x, &y);
switch(k){
case 1:{
update(root, 1, n, x, y);
break;
}
case 2:{
printf("%d
", query(root, 1, n, x, y));
break;
}
}
}
return 0;
}
区间修改+单点查询
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
//Mystery_Sky
//线段树模板（区间修改+单点查询）
#define M 5000050
#define ll long long
#define INF 0x3f3f3f3f
#define Mid (l+r)>>1
struct Tree{
Tree *lc, *rc;
int x, lazy;
}dizhi[M<<1], *root = &dizhi[0];
int n, m, t=1;
int a[M];
int x, y, d, k;
void build(Tree *tree, int l, int r)
{
if(l == r) {
tree->x = a[l];
return;
}
int mid = Mid;
tree->lc = &dizhi[++t];
tree->rc = &dizhi[++t];
build(tree->lc, l, mid);
build(tree->rc, mid+1, r);
tree->x = tree->lc->x + tree->rc->x;
}
inline void pushdown(Tree *tree, int l, int r)
{
if(!tree->lazy) return;
int mid = Mid;
tree->lc->x += tree->lazy * (mid - l + 1);
tree->rc->x += tree->lazy * (r - mid);
tree->lc->lazy += tree->lazy;
tree->rc->lazy += tree->lazy;
tree->lazy = 0;
}
void update(Tree *tree, int l, int r, int x, int y, int d)
{
if(x <= l && y >= r) {
tree->x += d * (r - l + 1);
tree->lazy += d;
return;
}
pushdown(tree, l, r);
int mid = Mid;
if(x <= mid) update(tree->lc, l, mid, x, y, d);
if(y > mid) update(tree->rc, mid+1, r, x, y, d);
tree->x = tree->lc->x + tree->rc->x;
}
int query(Tree *tree, int l, int r, int x)
{
if(l == r) {
return tree->x;
}
pushdown(tree, l, r);
int mid = Mid;
if(x <= mid) return query(tree->lc, l, mid, x);
else return query(tree->rc, mid+1, r, x);
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
build(root, 1, n);
for(int i = 1; i <= m; i++) {
scanf("%d", &k);
switch(k) {
case 1:{
scanf("%d%d%d", &x, &y, &d);
update(root, 1, n, x, y, d);
break;
}
case 2:{
scanf("%d", &x);
printf("%d
", query(root, 1, n, x));
break;
}
}
}
return 0;
}
区间修改+区间查询
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
//Mystery_Sky
//线段树模板（区间修改+区间查询）
#define M 5000050
#define ll long long
#define INF 0x3f3f3f3f
#define Mid (l+r)>>1
struct Tree{
Tree *lc, *rc;
ll x, lazy;
}dizhi[M<<1], *root = &dizhi[0];
int n, m, t=1;
int a[M];
int x, y, d, k;
void build(Tree *tree, int l, int r)
{
if(l == r) {
tree->x = a[l];
return;
}
int mid = Mid;
tree->lc = &dizhi[++t];
tree->rc = &dizhi[++t];
build(tree->lc, l, mid);
build(tree->rc, mid+1, r);
tree->x = tree->lc->x + tree->rc->x;
}
inline void pushdown(Tree *tree, int l, int r)
{
if(!tree->lazy) return;
int mid = Mid;
tree->lc->x += tree->lazy * (mid - l + 1);
tree->rc->x += tree->lazy * (r - mid);
tree->lc->lazy += tree->lazy;
tree->rc->lazy += tree->lazy;
tree->lazy = 0;
}
void update(Tree *tree, int l, int r, int x, int y, int d)
{
if(x <= l && y >= r) {
tree->x += (ll) d * (r - l + 1);
tree->lazy += d;
return;
}
pushdown(tree, l, r);
int mid = Mid;
if(x <= mid) update(tree->lc, l, mid, x, y, d);
if(y > mid) update(tree->rc, mid+1, r, x, y, d);
tree->x = tree->lc->x + tree->rc->x;
}
ll query(Tree *tree, int l, int r, int x, int y)
{
if(x <= l && y >= r) {
return tree->x;
}
pushdown(tree, l, r);
int mid = Mid;
ll ans = 0;
if(x <= mid) ans += query(tree->lc, l, mid, x, y);
if(y > mid) ans += query(tree->rc, mid+1, r, x, y);
return ans;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
build(root, 1, n);
for(int i = 1; i <= m; i++) {
scanf("%d", &k);
switch(k) {
case 1:{
scanf("%d%d%d", &x, &y, &d);
update(root, 1, n, x, y, d);
break;
}
case 2:{
scanf("%d%d", &x, &y);
printf("%lld
", query(root, 1, n, x, y));
break;
}
}
}
return 0;
}
区间乘+区间加+区间查询
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
//Mystery_Sky
//
#define INF 0x3f3f3f3f
#define M 1000005
#define ll long long
#define Mid (l+r)>>1
inline ll read()
{
ll x=0,f=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
struct Tree{
Tree *lc, *rc;
ll x;
ll lazyp, lazym;
}dizhi[M<<1], *root = &dizhi[0];
int t=1;
int n, m, p;
ll a[M];
inline void push_up(Tree *tree) {tree->x = (tree->lc->x + tree->rc->x) % p;}
inline void build(Tree *tree, int l, int r)
{
if(l == r) {
tree->x = a[l];
tree->lazym = 1;
return;
}
int mid = Mid;
tree->lazym = 1;
tree->lc = &dizhi[t++];
tree->rc = &dizhi[t++];
build(tree->lc, l, mid);
build(tree->rc, mid+1, r);
push_up(tree);
}
inline void push_down(Tree *tree, int l, int r)
{
if((tree->lazyp == 0 && tree->lazym == 1) || tree->lc == NULL) return;
int mid = Mid;
tree->lc->x = ((tree->lc->x * tree->lazym) % p + (ll)tree->lazyp * (mid - l + 1)) % p;
tree->rc->x = ((tree->rc->x * tree->lazym) % p + (ll)tree->lazyp * (r - mid)) % p;
tree->lc->lazym = (tree->lc->lazym * tree->lazym) % p;
tree->rc->lazym = (tree->rc->lazym * tree->lazym) % p;
tree->lc->lazyp = ((ll)tree->lc->lazyp * tree->lazym + tree->lazyp) % p;
tree->rc->lazyp = ((ll)tree->rc->lazyp * tree->lazym + tree->lazyp) % p;
tree->lazyp = 0;
tree->lazym = 1;
return;
}
inline void add(Tree *tree, int l, int r, int x, int y, int d)
{
if(x <= l && y >= r) {
tree->x = (tree->x + (ll) d * (r - l + 1)) % p;
tree->lazyp = (tree->lazyp + d) % p;
return;
}
push_down(tree, l, r);
int mid = Mid;
if(x <= mid) add(tree->lc, l, mid, x, y, d);
if(y > mid) add(tree->rc, mid+1, r, x, y, d);
push_up(tree);
}
inline void multi(Tree *tree, int l, int r, int x, int y, int d)
{
if(x <= l && y >= r) {
if(tree->lazyp) push_down(tree, l, r);
tree->x = (tree->x * d) % p;
tree->lazym = (tree->lazym * d) % p;
return;
}
push_down(tree, l, r);
int mid = Mid;
if(x <= mid) multi(tree->lc, l, mid, x, y, d);
if(y > mid) multi(tree->rc, mid+1, r, x, y, d);
push_up(tree);
}
inline ll query(Tree *tree, int l, int r, int x, int y)
{
if(x <= l && y >= r) return tree->x;
push_down(tree, l, r);
int mid = Mid;
ll ret = 0;
if(x <= mid) ret = (ret + query(tree->lc, l, mid, x, y)) % p;
if(y > mid) ret = (ret + query(tree->rc, mid+1, r, x, y));
return ret % p;
}
int main() {
n = read(), m = read(), p = read();
for(int i = 1; i <= n; i++) a[i] = read();
build(root, 1, n);
for(int i = 1; i <= m; i++) {
int opt = read();
if(opt == 1) {
int x = read(), y = read(), k = read();
multi(root, 1, n, x, y, k);
}
else if(opt == 2) {
int x = read(), y = read(), k = read();
add(root, 1, n, x, y, k);
}
else {
int x = read(), y = read();
printf("%lld
", query(root, 1, n, x, y));
}
}
return 0;
}