[POJ] 3468. A Simple Problem with Integers
題目連結:http://poj.org/problem?id=3468
裸的線段樹,區間加值、區間查和,不過也可以用BIT做掉,不過我不太會QQ
裸的線段樹,區間加值、區間查和,不過也可以用BIT做掉,不過我不太會QQ
#include <iostream>
#include <utility>
using namespace std;
typedef long long lld;
typedef pair<lld,lld> PLL;
#define FF first
#define SS second
const int N = 100000 + 5;
class SegTree{
private:
PLL nodes[N<<2];
int size;
inline int lc(int x){return (x<<1)+1;}
inline int rc(int x){return (x<<1)+2;}
inline void push(int l, int r, int id){
if(r-l>1){
nodes[lc(id)].FF += nodes[id].FF;
nodes[rc(id)].FF += nodes[id].FF;
}
nodes[id].SS += nodes[id].FF * (r-l);
nodes[id].FF=0;
}
inline void pull(int l, int r,int id){
int mid=(l+r)>>1;
lld ll = nodes[lc(id)].SS+nodes[lc(id)].FF*(mid-l);
lld rr = nodes[rc(id)].SS+nodes[rc(id)].FF*(r-mid);
nodes[id].SS = ll + rr;
}
template<typename T>
void build(T* arr, int l, int r, int id){
nodes[id].FF=0;
if(r-l==1){
nodes[id].SS = arr[l];
}else{
int mid=(l+r)>>1;
build(arr, l, mid, lc(id));
build(arr, mid, r, rc(id));
nodes[id].SS = nodes[lc(id)].SS+nodes[rc(id)].SS;
}
}
lld query(int ql, int qr, int l, int r, int id){
if(r <= ql or qr <= l) return 0;
push(l,r,id);
if(ql <= l and r <= qr) return nodes[id].SS;
int mid=(l+r)>>1;
return query(ql, qr, l, mid, lc(id))+query(ql, qr, mid, r, rc(id));
}
void modify(int ql, int qr, int l, int r, int v, int id){
if(r <= ql or qr <= l) return;
push(l, r, id);
if(ql <= l and r <= qr){
nodes[id].FF = v;
return;
}
int mid=(l+r)>>1;
modify(ql, qr, l, mid, v, lc(id));
modify(ql, qr, mid, r, v, rc(id));
pull(l, r, id);
}
public:
template<typename T>
void build(T* arr, int n){
size=n;
build(arr, 0, n, 0);
}
lld query(int l,int r){
return query(l, r, 0, size, 0);
}
void modify(int l, int r, int v){
modify(l, r, 0, size, v, 0);
}
} seg;
int arr[N];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n, q; cin>>n>>q;
for(int i=0;i<n;i++) cin>>arr[i];
seg.build(arr,n);
while(q--){
char type;cin>>type;
if(type=='C'){
int l, r, v;cin>>l>>r>>v;
seg.modify(l-1,r,v);
}else if(type=='Q'){
int l, r;cin>>l>>r;
cout<<seg.query(l-1,r)<<'\n';
}
}
return 0;
}
留言
張貼留言