【原创】洛谷 LUOGU P3373 【模板】线段树2
2024-09-05 03:14:36
P3373 【模板】线段树 2
题目描述
如题,已知一个数列,你需要进行下面两种操作:
1.将某区间每一个数加上x
2.将某区间每一个数乘上x
3.求出某区间每一个数的和
输入输出格式
输入格式:
第一行包含三个整数N、M、P,分别表示该数列数字的个数、操作的总个数和模数。
第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数,表示一个操作,具体如下:
操作1: 格式:1 x y k 含义:将区间[x,y]内每个数乘上k
操作2: 格式:2 x y k 含义:将区间[x,y]内每个数加上k
操作3: 格式:3 x y 含义:输出区间[x,y]内每个数的和对P取模所得的结果
输出格式:
输出包含若干行整数,即为所有操作3的结果。
输入输出样例
输入样例#1:
5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4
输出样例#1:
17
2
说明
时空限制:1000ms,128M
数据规模:
对于30%的数据:N<=8,M<=10
对于70%的数据:N<=1000,M<=10000
对于100%的数据:N<=100000,M<=100000
(数据已经过加强^_^)
样例说明:
故输出应为17、2(40 mod 38=2)
乘法的优先级永远比加法高。
代码如下:
// LUOGU 3373 【模板】线段树2
// 2017.7.20 20:52
#include<bits/stdc++.h>
#define INF 0x3fffffff
#define MAXN 100000
#define MAXT MAXN*4
using namespace std;
typedef long long ll;
int N,M,topt=;
ll P,a[MAXN+];
struct sgt_node{
int lc,rc;
ll sum,pls,mul;
sgt_node(){pls=,mul=INF;}
}sgt[MAXT+];
int getint(){
char ch='*';
while(!isdigit(ch=getchar()));
int num=ch-'';
while(isdigit(ch=getchar()))num=num*+ch-'';
return num;
}
ll getll(){
char ch='*';
while(!isdigit(ch=getchar()));
ll num=ch-'';
while(isdigit(ch=getchar()))num=num*+ch-'';
return num;
}
#define lch sgt[now].lc
#define rch sgt[now].rc
#define smid ((l+r)>>1)
void update(int now){
sgt[now].sum=(sgt[lch].sum+sgt[rch].sum)%P;
}
void set_mul(int now,ll v){
sgt[now].sum=(sgt[now].sum*v)%P;
if(sgt[now].mul==INF)sgt[now].mul=v%P;
else sgt[now].mul=(sgt[now].mul*v)%P; // 必须为乘法!!!
sgt[now].pls=(sgt[now].pls*v)%P;
}
void set_pls(int now,int l,int r,ll v){
sgt[now].sum=(sgt[now].sum+v*(r-l+))%P;
sgt[now].pls=(sgt[now].pls+v)%P;
}
void push_down(int now,int l,int r){
if(sgt[now].mul!=INF){
set_mul(lch,sgt[now].mul);
set_mul(rch,sgt[now].mul);
sgt[now].mul=INF;
}
if(sgt[now].pls){
set_pls(lch,l,smid,sgt[now].pls);
set_pls(rch,smid+,r,sgt[now].pls);
sgt[now].pls=;
}
}
void Build_sgt(int &now,int l,int r){
now=++topt;
if(l==r){
sgt[now].sum=a[l];
return;
}
Build_sgt(lch,l,smid);
Build_sgt(rch,smid+,r);
update(now);
}
ll Query_sgt(int now,int l,int r,int qx,int qy){
if(l==qx&&r==qy)return sgt[now].sum;
push_down(now,l,r);
if(qy<=smid)return Query_sgt(lch,l,smid,qx,qy);
if(qx>smid)return Query_sgt(rch,smid+,r,qx,qy);
return Query_sgt(lch,l,smid,qx,smid)+Query_sgt(rch,smid+,r,smid+,qy);
}
void Region_mul(int now,int l,int r,int x,int y,ll v){
if(l==x&&r==y){
set_mul(now,v);
return;
}
push_down(now,l,r);
if(y<=smid)Region_mul(lch,l,smid,x,y,v);
else if(x>smid)Region_mul(rch,smid+,r,x,y,v);
else{
Region_mul(lch,l,smid,x,smid,v);
Region_mul(rch,smid+,r,smid+,y,v);
}
update(now);
}
void Region_pls(int now,int l,int r,int x,int y,ll v){
if(l==x&&r==y){
set_pls(now,l,r,v);
return;
}
push_down(now,l,r);
if(y<=smid)Region_pls(lch,l,smid,x,y,v);
else if(x>smid)Region_pls(rch,smid+,r,x,y,v);
else{
Region_pls(lch,l,smid,x,smid,v);
Region_pls(rch,smid+,r,smid+,y,v);
}
update(now);
}
int main(){
N=getint(),M=getint(),P=getll();
for(int i=;i<=N;i++)
a[i]=getll();
int root=;
Build_sgt(root,,N);
int op,x,y;
ll k;
for(int i=;i<=M;i++){
op=getint();
switch(op){
case :
x=getint(),y=getint(),k=getll();
Region_mul(,,N,x,y,k);
break;
case :
x=getint(),y=getint(),k=getll();
Region_pls(,,N,x,y,k);
break;
case :
x=getint(),y=getint();
printf("%lld\n",Query_sgt(,,N,x,y)%P);
break;
}
}
return ;
}
最新文章
- php的面向对象
- Windows 版本的iTunes 修改iPhone的备份路径
- ios - 文件保存路径的获取
- Codeforces Round #306 (Div. 2) C. Divisibility by Eight 暴力
- REST接口规范
- java之jvm学习笔记十三(jvm基本结构)
- [Log函数]C++log函数使用
- python多态和规范
- .net 项目与网站区别
- Oracle 11g数据库的创建
- 个人项目Individual Project:迷宫求解
- 为什么要使用getter/setter
- 《DSP using MATLAB》Problem 5.24-5.25-5.26
- docker之docker-machine用法
- CSS中的通用字体
- Git-根据tag创建分支
- node.js+express,实现RESTful API
- 【页面加速】配置Nginx加载ngx_pagespeed模块,加快网站打开的速度
- nacicat premium 快捷键
- 我的Vue之小功能统计