Codeforces Round #254 (Div. 2)E题这题说的是给了一个一段连续的区间每个区间有一种颜色然后一个彩笔从L画到R每个区间的颜色都发生了 改变然后 在L和R这部分区间里所用的颜色变成了x 然后每个区间的 色度加上abs(x-Yi) Yi 为原位置的颜色,还有一个操作就是求 L 到 R 的距离之内的所有的点和,数据 有 n<=100000 m<100000 次操作 对于每次第二种操作输出, 自然我们将一个区间的颜色如果相同自然将他们 用延迟标记 但是 会有一个问题就是在一个带有延迟标记的区间操作两次或者两次以上会然后再去求这个延迟标记的某个区间的时候我们将无法进行,这里我们稍加修改就得到了我们想要的 就是 sum=(sum[o]-sum[lc]-sum[rc)/(R-L+1)这样就得到了我们对于每个子区间的再添加两次后的个数平均值然后进行一次向下的传递就ok了 这样每个区间得到了值sum[lc]+=sum*(lc->R - lc->L + 1); sum[rc] += sum*(rc->R - rc->L +1) 然后得到向下传递的值
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
const int maxn =;
__int64 _sum,x;
int n,m,op,y1,y2;
struct Itree{
__int64 sumv[maxn],color[maxn];
bool mark[maxn];
__int64 abs(__int64 a,__int64 b){
return (a-b)>?(a-b):(b-a);
}
void build(int o, int L, int R){
if(L == R){
color[o]=L;
sumv[o] =;
mark[o] =true;
return ;
}
int M = L + ((R-L)>>) ;
build(o*, L, M);
build(o*+, M+, R);
mark[o] = false;
sumv[o] = ;
}
void pushdown(int o,int L,int R){
int lc=o*,rc=o*+;
__int64 sum= sumv[lc]+sumv[rc];
sum = (sumv[o]-sum)/(R-L+);
int M=L+((R-L)>>);
color[lc]=color[rc]=color[o];
sumv[lc]+=1LL*(M-L+)*sum;
sumv[rc]+=1LL*(R-M)*sum;
mark[lc]=mark[rc]=true;
}
void update(int o,int L, int R){
int lc = o* , rc = o* + ;
if(y1<=L&&y2>=R&&mark[o]==true){
sumv[o] += 1LL*(R-L+)*abs(color[o],x);
color[o]=x;
mark[o]=true;
}
else{
if(mark[o]==true) pushdown(o,L,R);
mark[o] = false;
int M =L+((R-L)>>);
if(y1<=M)update(lc,L,M);
if(y2>M) update(rc,M+,R);
if(y1<=L&&y2>=R){
color[o]=x; mark[o]=true;
}
sumv[o]=sumv[lc]+sumv[rc];
}
}
void query(int o, int L, int R){
int lc =o*,rc =o*+;
if(y1<=L && y2>=R){
_sum+=sumv[o];
}else{
if(mark[o]==true) pushdown(o,L,R);
mark[o]=false;
int M = L + ( (R-L)>> );
if(y1 <= M) query(lc,L,M);
if(y2 > M) query(rc,M+,R);
}
}
}tree;
int main()
{ int n,m;
scanf("%d%d",&n,&m);
tree.build(,,n);
for(int i =; i<m; ++i){
scanf("%d%d%d",&op,&y1,&y2);
if(op==){
scanf("%I64d",&x);
tree.update(,,n);
}else{
_sum=;
tree.query(,,n);
printf("%I64d\n",_sum);
}
}
return ;
}
uva12299 这 题 说 的 是 给 了 一 个 数 字 数 组 要 求 找 出 某 个 区 间 内 的 最 小 值 然 后 还 有 一 个 操 作 是 循 环 的 置换 选 中 的 几 个 数 字 然 后 使 用 线 段 树 的 单 点 更 新 查询用线段树 查找
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
const int maxn =;
int C[maxn];
int tem,y1,y2,v,_min;
struct Itree{
int minv[maxn*];
void build(int o,int L,int R){
if(L==R){
scanf("%d",&minv[o]);
C[L]=minv[o];
return ;
}
int lc=o<<,rc=(o<<)|;
int M=L+( (R-L)>> );
build(lc,L,M);
build(rc,M+,R);
minv[o]=min( minv[lc], minv[rc] );
}
void query(int o,int L,int R){
int lc=o<<,rc=(o<<)|;
if(y1<=L&&y2>=R){
_min=min(_min,minv[o]);
}
else{
int M=L+((R-L)>>);
if(y1<=M) query(lc,L,M);
if(y2 >M) query(rc,M+,R);
}
}
void update(int o,int L,int R){
int lc=o<<,rc=(o<<)|;
if(L==R){
minv[o]=v;
}
else{
int M=L+((R-L)>>);
if(tem<=M) update(lc,L,M);
else update(rc,M+,R);
minv[o]=min(minv[lc],minv[rc]);
}
}
}tree;
char str[];
int rt[],len;
int worth[];
void jud(){
len=;
int L =strlen(str);
int i=;
while(i<L){ if(str[i]>=''&&str[i]<=''){
int E = ;
while( str[i] >= '' && str[i] <= ''&&i<L){
E= E * + str[i] - '';
++i;
}
rt[len++]=E;
}
++i;
}
}
int main()
{
int n,q;
while( scanf("%d%d",&n,&q) == ){
tree.build(,,n);
getchar();
for(int i =; i<q; ++i){
gets(str);
len=;
jud();
if(str[]=='q'){
y1=rt[]; y2=rt[];
_min=;
tree.query(,,n);
printf("%d\n",_min);
}else{
for(int x =; x<len; ++x)
worth[x]=C[rt[(x+)%len]];
for(int x =; x< len ;++x){
tem=rt[x]; v=worth[x];
tree.update(,,n);
}
for(int x =; x<len; ++x){
C[rt[x]]=worth[x];
}
}
}
} return ;
}
uva1232 这题说的是给 我们要在地平线上依次建造n座建筑物.建筑物的修建按照从后往前的顺序,因此新建物可能会挡住一部分的老建筑修建完一座建筑物之后,统计他在多长的部分是最高的可以等高并把这个长度称为该建筑物的覆盖度,接下来对线段树进行稍加修改就ok了 然后记得 不要用区间去表示 将他给的点缩成 L,R-1 建树的时候同样用这样的操作
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
const int maxn = ;
int L[],R[],C[];
int y1,y2,v,_sum;
struct Itree{
int maxv[maxn],setv[maxn];
void pushdown(int o){
int lc = o<< , rc = (o<<)|;
if(setv[o]>=){
setv[lc]=setv[rc]=setv[o];
setv[o]=-;
}
}
void maintain(int o, int L, int R){
int lc = o<<, rc=(o<<)|;
if(R>L){
maxv[o]=max(maxv[lc], maxv[rc]);
}
if(setv[o]>=){
maxv[o]=setv[o];
}
}
void query(int o,int L,int R){ int lc =o<<, rc =( o<< )|;
maintain(o, L, R);
if(setv[o]>v) return;
if(setv[o]==v){
_sum+=min(R,y2) - max(L,y1) + ;
return ;
}
if( y1 <= L && y2 >= R && maxv[o]<=v ){
_sum+=R-L+;
setv[o]=v;
} else {
int M =L+((R-L)>>); pushdown( o ); if(y1<=M) query(lc,L,M);
else maintain(lc,L,M); if(y2 >M) query(rc,M+,R);
else maintain(rc,M+,R);
}
maintain(o,L,R);
} }tree;
int main()
{
int n,TR,ans,t;
scanf("%d",&t);
while(t --){
ans=;
scanf("%d",&n);
TR=;
for(int i =; i<n; ++i){
scanf("%d%d%d",&L[i],&R[i],&C[i]);
TR=max(R[i],TR);
}
tree.setv[]=;
TR--;
for(int i =;i<n; ++i){
_sum=;
v=C[i]; y1=L[i]; y2=R[i]-;
tree.query(,,TR);
ans+=_sum;
}
printf("%d\n",ans);
}
return ;
}
uva11525 这个题说的是给了1到K的数列 求出这个数列 的 第n 大 当然按照字典序排列, 因为 n=Si(k-i)!+Si-1(k-(i-1))!+...S0(k-k)! 经过分析我们可以得出这样的一个结论就是Si 代表的是剩下的第几大的数 用前段树去查询 每 次 找 到 相 应 的 k值
#include <iostream>
#include<cstdio>
#include <string.h>
using namespace std;
const int maxn = *;
int tem,_s,_k,S[],ans[];
struct Itree{
int sumv[maxn];
void build(int o,int L,int R){
if(L==R){
sumv[o]=; return ;
}
int M=L+((R-L)>>);
int lc=o<<,rc=(o<<)|;
build(lc, L, M);
build(rc, M+, R);
maintain(o,L,R);
}
void maintain(int o,int L,int R){
int lc = o<<, rc=(o<<)|;
if(R>L){
sumv[o] =sumv[lc]+sumv[rc];
}
}
void query(int o,int L, int R){
int lc = o<<, rc =(o<<)|;
if(L==R){
_s=L;
sumv[o]=; return;
}
int M = L+((R-L)>>);
if(sumv[lc]>=_k){
query(lc,L,M);
}else{
_k-=sumv[lc];
query(rc,M+,R);
}
maintain(o,L,R);
}
}tree;
int main()
{
int t,k;
scanf("%d",&t);
while(t--){
scanf("%d",&k);
tree.build(,,k);
for(int i =; i<k; ++i)
scanf("%d",&S[i]);
for(int i =; i<k; ++i){
_k=S[i]+;
tree.query(,,k);
ans[i]=_s;
}
for(int i =;i<k-; ++i)
printf("%d ",ans[i]);
printf("%d\n",ans[k-]);
}
return ;
}
uva11402 这题说的是 给了一排的 o1 串 有 3 种操作 1 将F L R L和R 之间的 变成1 E L R 将 L 和R 之间的变成 0 I 将 L 和 R 取 反, S L R 求 L 和 R 之间的 和 , 这样这个数 太大了有 1000000 个0 1 显然不能做 可是 他操作的区间只有 1000 个 通过离散操作区间求值 从而节省时间将 每 个 不 在 操 作 点 上 的 区 间 化 为 一 个 点 然 后 处理好值就ok了 离散了一下
#include <iostream>
#include <cstdio>
#include <string.h>
#include <set>
#include <map>
using namespace std;
const int maxn = *;
int interval[maxn][];
int y1,y2,_sum,v,op;
struct Itree
{
int setv[maxn],numv[maxn],ZER[maxn],ONE[maxn],addv[maxn];
void build(int o, int L, int R)
{
setv[o]=-;addv[o]=;
if(L==R)
{
ZER[o] = interval[L][] - interval[L][] ;
ONE[o] = interval[L][];
numv[o] = interval[L][];
return ;
}
int lc=o*,rc = o* + ;
int M =L+(R-L)/;
build(lc,L,M);
build(rc,M+,R);
ONE[o]=ONE[lc]+ONE[rc];
numv[o]=numv[lc]+numv[rc];
ZER[o]=numv[o]-ONE[o];
}
void pushdown(int o)
{
int lc = o*, rc =o*+;
if( setv[o] >= )
{
setv[lc]=setv[rc]=setv[o];
ONE[lc] = numv[lc]*setv[o];
ZER[lc] = numv[lc]-ONE[lc];
ONE[rc] = numv[rc]*setv[o];
ZER[rc] = numv[rc]-ONE[rc];
addv[lc]=addv[rc]=;
setv[o]=-;
}
if(addv[o]>){
addv[lc]=-addv[lc];
addv[rc]=-addv[rc];
swapp(ONE[lc],ZER[lc]);
swapp(ONE[rc],ZER[rc]);
addv[o]=;
}
}
void swapp(int &A,int &B){
int t =A; A=B; B=t;
}
void update(int o, int L, int R)
{
int lc=o*,rc=(o*)+;
if(y1 <=L && y2 >= R)
{
if(op==){
setv[o]=v;
addv[o]=;
ONE[o]=setv[o]*numv[o];
ZER[o]=numv[o]-ONE[o];
}else{
addv[o]=-addv[o];
swapp(ONE[o],ZER[o]);
}
}else{
int M=L+((R-L)/);
pushdown(o);
if(y1<=M)update(lc,L,M);
if(y2>M) update(rc,M+,R);
ONE[o]=ONE[lc]+ONE[rc];
ZER[o]=numv[o]-ONE[o];
}
}
void query(int o,int L,int R)
{
int lc =o*,rc=(o*)+;
if(y1<=L&&y2>=R)
{
_sum+= ONE[o];
}else {
int M =L+((R-L)/);
pushdown(o);
if(y1<=M)query(lc,L,M);
if(y2>M) query(rc,M+,R);
}
}
}tree;
char SE[],Q[][];
int LZ[],RZ[],duan;
int RE[],str[];
int main()
{ int T;
scanf("%d",&T);
for(int cas = ; cas <=T ; ++cas)
{
set<int>UN;
int len=,QR=,M;
printf("Case %d:\n",cas);
scanf("%d",&M);
for(int i =; i<M; ++i)
{
int tim,L ;
scanf("%d",&tim);
scanf("%s",SE);
L=strlen(SE);
for( int j = ; j < tim; ++ j )
for(int k =; k<L ; ++k)
str[len++] = SE[k]-'';
}
int qz;
scanf("%d",&qz);
for(int i =;i<qz ; ++ i)
{
scanf("%s%d%d",Q[i],&LZ[i],&RZ[i]);
UN.insert(LZ[i]);
UN.insert(RZ[i]);
}
UN.insert();
UN.insert(len-);
duan=;
set<int>::iterator it;
it=UN.begin();
int per = *it,fer;
++duan;
RE[per] = duan;
interval[duan][]=str[per];
interval[duan][]=;
++it;
for(; it!=UN.end(); ++it )
{
fer=*it;
int sT= per+,num=;
while(sT<fer)
{
if( str[sT] == )
num++;
sT++;
}
if( (fer-) > per )
{
duan++;
interval[duan][]=num;
interval[duan][]=fer--per;
}
duan++;
interval[duan][] = str[fer];
interval[duan][] = ;
RE[fer]=duan;
per=fer;
}
tree.build(,,duan);
for(int i =; i<qz; ++i )
{
y1 =RE[LZ[i]];
y2 =RE[RZ[i]];
if(Q[i][]=='F'){
op=;
v=;
tree.update(,,duan);
}
else if(Q[i][]=='E'){
op=;
v=;
tree.update(,,duan);
}else if( Q[i][] == 'I' ){
op=;
tree.update(,,duan);
}else {
_sum=;
tree.query(,,duan);
printf("Q%d: %d\n",++QR,_sum);
} }
UN.clear();
} return ;
}
uva1455 这题说的是在一个 平面上有n个城市,初始时城市之间没有任何的双向道路相连,你的任务是一次执行以下指令.
road A B: 在城市A 和城市B 之间连接一条双向道路,保证这条道路不和其他道路在非端点处相交.
line C 询问一条 y = c 的水平线和多少个州相交.本指令中,C的小数部分保证为0.5
通过将y坐标离散化,然后得到了许多的区间 然后 通过并查集不断地去维护这个区间, 每 两 个 区间 合 并 的 时 候 就该 去 判 断 区 间 与 区 间 之 间 的 联 系 然 后 得 到 最 终 的 更 新 目 的 这 题 变 成,了成段更新单点查询 这代码中有解释
#include <iostream>
#include <cstdio>
#include <string.h>
#include <set>
#include <algorithm>
using namespace std;
const int maxn= ;
struct point{
int x,y;
}Pcity[maxn];
int y1,y2,pv,zv,tem,_state,_city;
struct Itree
{
int city[maxn*],state[maxn*];
void build(int o,int L, int R)
{
city[o]=state[o]=;
if(L==R) return ;
int M = L+((R-L)>>);
build(o<<,L,M);
build((o<<)|,M+,R);
}
void pushdown(int o)
{
int lc =o<<, rc = (o<<)| ;
city[lc] += city[o];
city[rc] += city[o];
state[lc]+= state[o];
state[rc]+= state[o];
state[o] = city[o] = ;
}
void update(int o, int L, int R)
{
int lc=o<<, rc =(o<<)|;
if(y1<=L &&y2>=R)
{
state[o] += zv;
city[o] += pv;
}
else{
int M = L+((R-L)>>);
pushdown(o);
if( y1 <= M ) update(lc,L,M);
if( y2 > M ) update(rc,M+,R);
}
}
void query(int o, int L, int R)
{
int lc=o<<, rc=(o<<)|;
if(R==L){
_state = state[o];
_city = city[o];
return;
}
else {
int M = L + ( (R-L)>> );
pushdown( o );
if(tem<=M)query( lc, L, M );
else query( rc, M+, R );
}
}
}tree;
int C[],DOWNm[],UPm[],per[],len,num[];
char str[];
int RE[];
int finde(int x)
{
return per[x]==x?x:(per[x]=finde(per[x]));
}
void upoperator(int Lloc, int Rloc, int pvw, int zvw)
{
y1 = RE[Lloc]+; y2 =RE[Rloc];
pv = pvw; zv = zvw;
tree.update(,,len);
}
void intf(int p1, int p2)
{
int DOWN =min(DOWNm[p1],DOWNm[p2]) , UP= max(UPm[p1],UPm[p2]);
per[p1]=p2;
num[p2]+=num[p1];
DOWNm[p2]=DOWN; UPm[p2]=UP;
}
void OneToSet(int p1, int p2)
{
if( DOWNm[p1] >= DOWNm[p2] && DOWNm[p1] <= UPm[p2] )
{//p1点在 p2集合 区间内
upoperator( DOWNm[p2],UPm[p2],num[p1], );
intf(p1,p2);
return ;
}
if( DOWNm[p1] > UPm[p2] )
{// p1这个点在 p2集合的上面
upoperator(UPm[p2],DOWNm[p1],num[p2]+num[p1],);
upoperator(DOWNm[p2],UPm[p2],num[p1],);
intf(p1,p2);
return;
}
if( DOWNm[p1] < UPm[p2] )
{// p1 这个点在 p2集合的 下面
upoperator( DOWNm[p1], DOWNm[p2], num[p1]+num[p2], );
upoperator( DOWNm[p2], UPm[p2],num[p1],);
intf(p1,p2);
return ;
}
}
void intersect(int p1, int p2)
{
if(UPm[p1]-UPm[p2]>)
upoperator(UPm[p2], UPm[p1], num[p2],);
if(UPm[p2]-DOWNm[p1]>)
upoperator(DOWNm[p1],UPm[p2],,-);
if(DOWNm[p1]-DOWNm[p2]>)
upoperator(DOWNm[p2] , DOWNm[p1], num[p1],);
intf(p1,p2);
}
void SetToSet(int p1, int p2)
{
if( DOWNm[p1] > UPm[p2] )
{//相离 p1 在上面
upoperator( DOWNm[p1], UPm[p1], num[p2], );
upoperator( UPm[p2], DOWNm[p1], num[p2]+num[p1], );
upoperator( DOWNm[p2], UPm[p2], num[p1], );
intf(p1,p2); return ;
}
if( DOWNm[p2] > UPm[p1] )
{//相离 p2 在上面
upoperator(DOWNm[p2], UPm[p2], num[p1], );
upoperator(UPm[p1], DOWNm[p2], num[p1]+num[p2],);
upoperator(DOWNm[p1], UPm[p1], num[p2], );
intf(p1,p2);
return ;
}
if( DOWNm[p1] >= DOWNm[p2] && UPm[p1] <= UPm[p2] )
{//包含
if(UPm[p2] -UPm[p1]>)
upoperator(UPm[p1], UPm[p2] , num[p1],);
if(UPm[p1]-DOWNm[p1]>)
upoperator(DOWNm[p1],UPm[p1],,-);
if(DOWNm[p1]-DOWNm[p2]>)
upoperator(DOWNm[p2], DOWNm[p1], num[p1],);
intf(p1,p2); return ;
}
if( UPm[p1]>UPm[p2]) // 相交
intersect(p1,p2); // p1 在p2 的上面
else intersect(p2,p1); // p1 在p2 的下面
}
void solve1(int p1, int p2)
{
int fp1 =finde(p1);
int fp2 =finde(p2);
if(fp1 == fp2) return;
if( DOWNm[fp1] == UPm[fp1]&& DOWNm[fp2] == UPm[fp2] && DOWNm[fp1] == DOWNm[fp2] )
{ // fp1 和 fp2 都是各自在同一行的点 或者集合 但是 他们 在同一行
intf(fp1,fp2);
return ;
}
if(DOWNm[fp1]==UPm[fp1] && DOWNm[fp2]==UPm[fp2] && DOWNm[fp1] != DOWNm[fp2])
{// fp1 和 fp2 都是各自在同一行的点 或者集合 但是 他们 不在同一行
int DOWN= min(DOWNm[fp1],DOWNm[fp2]), UP =max(UPm[fp1],UPm[fp2]);
upoperator( DOWN, UP, num[fp2]+num[fp1], );
intf(fp1,fp2);return ;
}
if( DOWNm[fp1] == UPm[fp1] && DOWNm[fp2] != UPm[fp2] )
{// fp1 是一个点 fp2 是一个集合
OneToSet(fp1,fp2); return ;
}
if(DOWNm[fp1] != UPm[fp1] && DOWNm[fp2] == UPm[fp2])
{// fp2 是一个点 fp1 是一个集合
OneToSet(fp2,fp1); return ;
}
int R1 = UPm[fp1] - DOWNm[fp1],R2=UPm[fp2] - DOWNm[fp2]; // 剩下的只可能是两个集合 计算两个集合的大小
if(R1<=R2)
SetToSet(fp1,fp2); // fp1 的集合小于 fp2 的集合
else SetToSet(fp2,fp1); // fp2 的集合小于 fp1 的集合
}
void solve2(int h)
{
int t = lower_bound(C,C+len+,h) - C;
tem=t;
tree.query(,,len);
printf("%d %d\n",_state,_city);
}
int main()
{
int T,n;
scanf("%d",&T);
for(int cas =; cas <=T ; ++cas)
{
set<int> UN;
scanf("%d",&n);
for(int i =; i<n ;++i)
{
scanf("%d%d",&Pcity[i].x,&Pcity[i].y);
Pcity[i].y*=;
per[i]=i;
UPm[i] = DOWNm[i] = Pcity[i].y;
num[i]=;
UN.insert(Pcity[i].y);
}
UN.insert();UN.insert(*);
len=;
for(set<int>::iterator it = UN.begin(); it!=UN.end() ; ++it)
{
int to = *it;
RE[to] =len;
C[ len ++ ] = to;
}
len--;
tree.build(,,len);
memset(tree.city,,sizeof(tree.city));
memset(tree.state,,sizeof(tree.state));
int m;
scanf("%d",&m);
for(int i =; i<m; ++i)
{
scanf("%s",str);
if(str[]=='r')
{
int p1,p2;
scanf("%d%d",&p1,&p2);
solve1(p1,p2);
}
else
{
double red;
scanf("%lf",&red);
solve2(red*);
}
}
UN.clear();
}
return ;
}
446C DZY Loves Fibonacci Numbers 这题说的是给了一组数从1编号到n 每个数都有初值, 有两种操作分别是1 l r 将 l和r 区间内的数 相对应的每个位置加上斐波那契f[1] 到f[r-l+1],通过数学方法他们证出斐波那契的通项
然后
发现同余 然后
这个 然后接下来的我就知道了 通过求逆得到
这个 可以用线段树来解决 因为我们知道等比数列相加和仍然是等比 然后通过这个每个线段树都有一个标记 标记的是 该数列的第一项然后 向下更新的时候就是 让 per[lc]+=per[o] per[rc]=per[lc]*q^(M+1-L) 然后得到了正解 虽然和其他的原理相同 还是把他敲了一遍 如果是自己想出来的 那就更有成就感了
#include <cstdio>
#include <string.h>
#include <iostream>
using namespace std;
const __int64 mod = ;
const int maxn=;
__int64 q1=,q2=,req1=,req2=,Y=;
__int64 F[maxn],A[maxn];
__int64 pow_2(int n,__int64 q)
{
__int64 a=q;
__int64 ans=;
while(n>)
{
if(n&) ans=(ans*a)%mod;
a=(a*a)%mod;
n/=;
}
return ans;
}
__int64 _sum;
int y1,y2;
struct Itree
{
__int64 per[maxn*],fer[maxn*],sumv[maxn*],falg[maxn*],addv[maxn*];
void pushdown(int o,int L,int R)
{
int lc=o*,rc=o*+;
int M = (L+R)/;
if(falg[o])
{
if(per[o]!=){
per[lc]=( per[lc]+per[o])%mod;
per[rc]=( per[rc]+per[o]*F[M+-L])%mod;
per[o]=;
}
if(fer[o]!=){
fer[lc] = (fer[lc]+fer[o])%mod;
fer[rc] = (fer[rc]+fer[o]*A[M+-L])%mod;
fer[o]=;
}
falg[o]=false;
falg[lc]=true;
falg[rc]=true;
}
}
void maintain(int o,int L, int R)
{
int lc=o*,rc =o*+;
sumv[o]=;
if(falg[o])
{
__int64 qn1=F[R-L+];
__int64 qn2=A[R-L+];
__int64 t1 =( ( ( ( ( -qn1+ mod )%mod ) *req1 )%mod) *per[o] )%mod;
__int64 t2 =( ( ( ( ( -qn2+ mod )%mod ) *req2 )%mod) *fer[o] )%mod;
sumv[o]=( ( ( (t1-t2)%mod + mod )%mod ) * Y )%mod;
}
sumv[ o ] += addv[ o ] ;
if( L<R ){
sumv[o] += sumv[lc] + sumv[rc] ;
}
}
void update(int o,int L,int R)
{
int lc=o*,rc=o*+;
if(y1<=L&&y2>=R){
per[o] = (per[o]+(q1*F[L-y1])%mod)%mod;
fer[o] = (fer[o]+(q2*A[L-y1])%mod)%mod;
falg[o]=true;
}else{
int M =(L+R)/;
pushdown(o,L,R);
if(y1<=M)update(lc,L,M);
else maintain(lc,L,M);
if(y2>M)update(rc,M+,R);
else maintain(rc,M+,R);
}
maintain(o,L,R);
}
void query(int o,int L,int R)
{
int lc =o*, rc =o*+;
if(y1<=L&&y2>=R){
_sum=(_sum+sumv[o])%mod;
}else{
int M=(L+R)/;
pushdown(o,L,R);
maintain(lc,L,M);
maintain(rc,M+,R);
if(y1<=M)query(lc,L,M);
if(y2>M)query(rc,M+,R);
} }
void build(int o, int L, int R)
{
addv[o]=per[o]=fer[o]=;
falg[o]=false;
if(L==R){
scanf("%I64d",&sumv[o]);
addv[o]=sumv[o];
return;
}
int lc =o*,rc =o*+;
int M = (L+R)/;
build(lc,L,M);
build(rc,M+,R);
sumv[o]=sumv[lc]+sumv[rc];
}
}tree;
void gcd(__int64 a,__int64 b,__int64 &g,__int64 &x,__int64 &y)
{
if(b==){
g=a ; x=; y=;
}else{
gcd(b,a%b,g,y,x); y-=x*(a/b);
}
}
__int64 exd(__int64 a,__int64 b)
{
__int64 x,y,g;
gcd(a,b,g,x,y);
return g==?(x+b)%b:-;
}
__int64 C[],R[];
int main()
{ int n,m;
A[]=F[]=;
for(int i = ; i<=; ++i)
{
F[i]=(F[i-]*q1)%mod;
A[i]=(A[i-]*q2)%mod;
}
scanf("%d%d",&n,&m);
tree.build(,,n);
for(int i =; i<m; ++i)
{
int c;
scanf("%d%d%d",&c,&y1,&y2);
if(c==) tree.update(,,n);
else {
_sum=;
tree.query(,,n);
printf("%I64d\n",(_sum)%mod);
}
}
return ;
}
线段树(I tree)的更多相关文章
-
线段树 Interval Tree
一.线段树 线段树既是线段也是树,并且是一棵二叉树,每个结点是一条线段,每条线段的左右儿子线段分别是该线段的左半和右半区间,递归定义之后就是一棵线段树. 例题:给定N条线段,{[2, 5], [4, ...
-
『线段树 Segment Tree』
更新了基础部分 更新了\(lazytag\)标记的讲解 线段树 Segment Tree 今天来讲一下经典的线段树. 线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间 ...
-
线段树(Segment Tree)（转）
原文链接:线段树(Segment Tree) 1.概述 线段树,也叫区间树,是一个完全二叉树,它在各个节点保存一条线段(即“子数组”),因而常用于解决数列维护问题,基本能保证每个操作的复杂度为O(lg ...
-
BZOJ.4695.最假女选手(线段树 Segment tree Beats!)
题目链接 区间取\(\max,\ \min\)并维护区间和是普通线段树无法处理的. 对于操作二,维护区间最小值\(mn\).最小值个数\(t\).严格次小值\(se\). 当\(mn\geq x\)时 ...
-
【数据结构系列】线段树(Segment Tree)
一.线段树的定义 线段树,又名区间树,是一种二叉搜索树. 那么问题来了,啥是二叉搜索树呢? 对于一棵二叉树,若满足: ①它的左子树不空,则左子树上所有结点的值均小于它的根结点的值 ②若它的右子树不空, ...
-
线段树(segment tree)
线段树在一些acm题目中经常见到,这种数据结构主要应用在计算几何和地理信息系统中.下图就为一个线段树: (PS:可能你见过线段树的不同表示方式,但是都大同小异,根据自己的需要来建就行.) 1.线段树基 ...
-
浅谈线段树 Segment Tree
众所周知,线段树是algo中很重要的一项! 一.简介 线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点. 使用线段树可以快速的查找某一个节点在 ...
-
【POJ 2528】Mayor’s posters（线段树+离散化）
题目 给定每张海报的覆盖区间,按顺序覆盖后,最后有几张海报没有被其他海报完全覆盖.离散化处理完区间端点,排序后再给相差大于1的相邻端点之间再加一个点,再排序.线段树,tree[i]表示节点i对应区间是 ...
-
poj 3264 【线段树】
此题为入门级线段树 题意:给定Q(1<=Q<=200000)个数A1A2…AQ,多次求任一区间Ai-Aj中最大数和最小数的差 #include<algorithm> #incl ...
随机推荐
-
计算机视觉中的词袋模型(Bow,Bag-of-words)
计算机视觉中的词袋模型(Bow,Bag-of-words) Bag-of-words 读 'xw20084898的专栏'的blogBag-of-words model in computer visi ...
-
SQL GETDATE()日期格式化函数
Sql Server 中一个非常强大的日期格式化函数 Select CONVERT(varchar(100), GETDATE(), 0): 05 16 2006 10:57AMSelect CONV ...
- ps怎么把白色背景变透明
-
sb 讲解 (!(~+[])+{})[--[~+";";][+[]]*[~+[]] + ~~!+[]]+({}+[])[[~!+[]]*~+[]]
代码:(!(~+[])+{})[--[~+""][+[]]*[~+[]] + ~~!+[]]+({}+[])[[~!+[]]*~+[]] 输出sb. 分段解析: 首先解析s: (! ...
-
[C#]Base使用小记
base 关键字用于从派生类中访问基类的成员: • 调用基类上已被其他方法重写的方法. • 指定创建派生类实例时应调用的基类构造函数. 基类访问只能在构造函数.实例方法或实例属性访问器中进行. 从静态 ...
-
个人博客作业Week2（代码规范，代码复审）
Q:是否需要有代码规范 首先我们来搞清楚什么是“代码规范”,它和“代码风格”又有什么关系.依据个人的审美角度,我可能更喜欢在函数与函数之间空出一行,可能在命名习惯和代码注释上更加的internatio ...
-
ununtu 18.04 163 mirror
deb http://mirrors.163.com/ubuntu/ bionic main restricted deb http://mirrors.163.com/ubuntu/ bionic- ...
-
SQL中的float类型的数据
问题1. 如何在SQL中默认的使用float类型的数据 SQL中想要通过计算的方式最快的得到一个float类型的数据,只需要运算的其中一个值后面加上小数点就ok. 比如 :9/2=4 但是 :9/2 ...
-
WINDOWS防火墙开启后Ping不通
WINDOWS系统由于安全考虑,当开启防火墙时,默认不允许外主机对其进行ping功能,即别的电脑ping不通本机.别的主机ping不通本机是因为本机的防火墙关闭了ICMP回显功能,只要把这回显功能打开 ...
-
word record 4
word record 4 pledge p le g vt. 保证,许诺 snowflake falke->n. 小薄片:火花 deputy de piu ti n. 代理人,代表 etch ...