포인터 라인 트 리 bzoj 1798
2829 단어 데이터 구조
배열 의 본질은 포인터 이기 때문에 buid (tr, 1, n) 를 사용 할 수 있 습 니 다.
하나의 Tree * tr 포인터, tr [1] 은 이 포인터 가 가리 키 는 다음 위 치 를 말 합 니 다. 배열 을 여 는 tr 가 아니 라 루트 로 바 뀌 었 습 니 다.
#include
#include
#include
#include
#define ll long long
#define inf 1e9
#define md
#define N 100010
using namespace std;
struct Tree
{
ll cheng,jia,sum,sz;
int l,r;
Tree *left,*right;
} tr[4*N];
int cnt=0,p,a[N];
typedef long long Qtype;
void add(Tree *root,ll jia,ll cheng)
{
root->cheng=root->cheng*cheng%p;
root->jia=(root->jia*cheng+jia)%p;
root->sum=(root->sum*cheng+root->sz*jia)%p;
}
void release(Tree *root)
{
Tree *l=root->left,*r=root->right;
ll jia=root->jia,cheng=root->cheng;
root->jia=0; root->cheng=1;
if (l!=NULL) add(l,jia,cheng);
if (r!=NULL) add(r,jia,cheng);
}
void update(Tree *root)
{
root->sum=0;
if (root->left!=NULL) root->sum+=root->left->sum;
if (root->right!=NULL) root->sum+=root->right->sum;
if (root->sum>=p) root->sum-=p;
}
void build(Tree *root,int l,int r)
{
root->sz=r-l+1; root->jia=0; root->cheng=1; root->l=l; root->r=r;
if (l==r)
{
root->left=root->right=NULL;
add(root,a[l],1);
return;
}
int mid=(l+r)>>1;
root->left=&tr[++cnt];
root->right=&tr[++cnt];
build(root->left,l,mid); build(root->right,mid+1,r);
update(root);
}
void modify(Tree *root,int l,int r,int ql,int qr,ll jia,ll cheng)
{
if (ql<=l&&r<=qr)
{
add(root,jia,cheng);
return;
}
release(root);
int mid=(l+r)>>1;
if (ql<=mid) modify(root->left,l,mid,ql,qr,jia,cheng);
if (mid+1<=qr) modify(root->right,mid+1,r,ql,qr,jia,cheng);
update(root);
}
Qtype query(Tree *root,int l,int r,int ql,int qr)
{
if (ql<=l&&r<=qr) return root->sum;
release(root);
int mid=(l+r)>>1;
if (qr<=mid) return query(root->left,l,mid,ql,qr);
if (mid+1<=ql) return query(root->right,mid+1,r,ql,qr);
return (query(root->left,l,mid,ql,qr)+query(root->right,mid+1,r,ql,qr))%p;
}
int main()
{
//freopen("a.in","r",stdin); //freopen("","w",stdout);
int n,m;
scanf("%d%d",&n,&p);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
build(tr,1,n);
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
int ty,l,r,d;
scanf("%d",&ty);
if (ty==1)
{
scanf("%d%d%d",&l,&r,&d);
modify(tr,1,n,l,r,0,d);
}
else if (ty==2)
{
scanf("%d%d%d",&l,&r,&d);
modify(tr,1,n,l,r,d,1);
}
else
{
scanf("%d%d",&l,&r);
printf("%lld
",query(tr,1,n,l,r)%p);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.