BZOJ 1798 AHOI 2009 Seq 유지 보수 시퀀스 세그먼트 트리
3482 단어 세그먼트 트리bzojzkw 세그먼트 트리BZOJ1798
1. 구간의 각 점의 값을 한 수에 곱하기
2. 구간에 있는 각 점의 값을 하나의 수로 덧붙인다
3. 구간의 p모드에 대한 값을 구한다
2631의 초^n급 약화판, 2631을 쓰기 전에 이 연습을 할 수 있습니다...
라인 트리 구간 수정은 학교의 대신이 ZKW의 구간 수정 방법을 지도하게 하여 이해하기 쉬웠지만 코드가 빠르지 못했다...나중에 코드를 고쳐볼게요. 제가 너무 엉망으로 썼나 봐요.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 100100
using namespace std;
typedef long long ll;
struct abcd{
ll sum,siz,add_mark,times_mark;
void add(ll x);
void times(ll x);
}tree[263000];
int m,n,p,q;
void abcd :: add(ll x)
{
sum+=x*siz;
sum%=p;
add_mark+=x;
add_mark%=p;
}
void abcd :: times(ll x)
{
sum*=x;
sum%=p;
add_mark*=x;
add_mark%=p;
times_mark*=x;
times_mark%=p;
}
void Build_Tree()
{
int i;
for(i=q+1;i<=q+n;i++)
{
scanf("%d",&tree[i].sum);
tree[i].siz=1;
tree[i].add_mark=0;
tree[i].times_mark=1;
}
for(i=q-1;i;i--)
{
tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
tree[i].sum%=p;
tree[i].siz=tree[i<<1].siz+tree[i<<1|1].siz;
tree[i].add_mark=0;
tree[i].times_mark=1;
}
}
int stack[M],top;
void Push_Down(int x)
{
if(x>=q)
return ;
if(tree[x].times_mark^1)
{
tree[x<<1 ].times(tree[x].times_mark);
tree[x<<1|1].times(tree[x].times_mark);
tree[x].times_mark=1;
}
if(tree[x].add_mark)
{
tree[x<<1 ].add(tree[x].add_mark);
tree[x<<1|1].add(tree[x].add_mark);
tree[x].add_mark=0;
}
}
void Push_Down(int x,int y)
{
for(x+=q-1,y+=q+1;x^y;x>>=1,y>>=1)
stack[++top]=x,stack[++top]=y;
for(;x;x>>=1)
stack[++top]=x;
while(top)
Push_Down(stack[top--]);
}
void Add(int x,int y,ll z)
{
for(x+=q-1,y+=q+1;x^y^1;x>>=1,y>>=1)
{
if(~x&1)tree[x^1].add(z);
if( y&1)tree[y^1].add(z);
}
}
void Times(int x,int y,ll z)
{
for(x+=q-1,y+=q+1;x^y^1;x>>=1,y>>=1)
{
if(~x&1)tree[x^1].times(z);
if( y&1)tree[y^1].times(z);
}
}
void Push_Up(int x)
{
if(x>=q)
return ;
tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;
tree[x].sum%=p;
}
void Push_Up(int x,int y)
{
for(x+=q-1,y+=q+1;x^y;x>>=1,y>>=1)
Push_Up(x),Push_Up(y);
for(;x;x>>=1)
Push_Up(x);
}
ll Get_Ans(int x,int y)
{
int re=0;
for(x+=q-1,y+=q+1;x^y^1;x>>=1,y>>=1)
{
if(~x&1)re+=tree[x^1].sum,re%=p;
if( y&1)re+=tree[y^1].sum,re%=p;
}
return re;
}
int main()
{
int i,x,y,c;
ll z;
cin>>n>>p;
for(q=1;q<=n+1;q<<=1);
Build_Tree();
cin>>m;
for(i=1;i<=m;i++)
{
scanf("%d",&c);
if(c==1)
{
scanf("%d%d%lld",&x,&y,&z);
Push_Down(x,y);
Times(x,y,z);
Push_Up(x,y);
}
else if(c==2)
{
scanf("%d%d%lld",&x,&y,&z);
Push_Down(x,y);
Add(x,y,z);
Push_Up(x,y);
}
else
{
scanf("%d%d",&x,&y);
Push_Down(x,y);
printf("%lld
", Get_Ans(x,y) );
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
백준 알고리즘 14427번 : 수열과 쿼리 15길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.