주석 트 리 수정 가능
다음은 코드 () 를 첨부 합 니 다.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define MAXN 100010
typedef double LL;
using namespace std;
struct node{
LL v1,v2,v3;
int v4;
int l,r,tot;
}tree[4000010];
int root[1010],tot,h[MAXN],f[11],k,n,m;
LL ans;
int get(){
char ch;
while (ch=getchar(),(ch<'0'||ch>'9')&& ch!='-');
char c=ch;
int s;
if (c!='-')s=c-48;else s=0;
while (ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-48;
return c=='-'?-s:s;
}
void inse(int l,int r,int &t,int x,int y,int tim){
if (!t)t=++tot;
tree[t].tot+=tim;
if (l==r){
if (x>y){
tree[t].v1+=LL(1)/(x-y)*tim;
tree[t].v2+=LL(y)/(x-y)*tim;
tree[t].v3+=LL(y*y)/(x-y)*tim;
}
tree[t].v4+=(x+y)*tim;
return;
}
int mid=(l+r)/2;
if (x<=mid)inse(l,mid,tree[t].l,x,y,tim);
else inse(mid+1,r,tree[t].r,x,y,tim);
int ls=tree[t].l,rs=tree[t].r;
tree[t].v1=tree[ls].v1+tree[rs].v1;
tree[t].v2=tree[ls].v2+tree[rs].v2;
tree[t].v3=tree[ls].v3+tree[rs].v3;
tree[t].v4=tree[ls].v4+tree[rs].v4;
}
void add(int x,int y,int tim){
int y1=y;
while (y<1001){
inse(1,1001,root[y],x,y1,tim);
y=y+(y& -y);
}
}
void cc(int i,int x){
if (iif (h[i]>h[i+1])add(h[i],h[i+1],-1);
else add(h[i+1],h[i],-1);
if (x1])add(h[i+1],x,1);
else add(x,h[i+1],1);
}
if (i>1){
if (h[i-1]>h[i])add(h[i-1],h[i],-1);
else add(h[i],h[i-1],-1);
if (x1])add(h[i-1],x,1);
else add(x,h[i-1],1);
}
h[i]=x;
}
void getl(){
fo(i,1,k)f[i]=tree[f[i]].l;
}
void getr(){
fo(i,1,k)f[i]=tree[f[i]].r;
}
void getanswer(int l,int r,int x){
if (l>x){
fo(i,1,k)ans=ans+0.5*(tree[f[i]].v1*x*x-tree[f[i]].v2*x*2+tree[f[i]].v3);
return;
}
if (r<=x){
fo(i,1,k)ans=ans+tree[f[i]].tot*x-0.5*tree[f[i]].v4;
return;
}
int tt[11];
fo(i,1,k)tt[i]=f[i];
getl();
int mid=(l+r)/2;
getanswer(l,mid,x);
fo(i,1,k)f[i]=tt[i];
getr();
getanswer(mid+1,r,x);
}
void getans(int x){
k=0;
int y=x;
while (y){
f[++k]=root[y];
y=y-(y & -y);
}
ans=0;
getanswer(1,1001,x);
}
int main(){
n=get();m=get();
fo(i,1,n)h[i]=get()+1;
fo(i,1,n-1)
if (h[i]1])add(h[i+1],h[i],1);
else add(h[i],h[i+1],1);
fo(i,1,m){
char ch;
while (ch=getchar(),ch!='Q'&&ch!='U');
if (ch=='Q'){
int x=get()+1;
getans(x);
printf("%.3lf
",ans);
}
else{
int x=get()+1,y=get()+1;
cc(x,y);
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
bzoj 3196 tyvj 1730 2 강 평형 수그 중에서 다음 과 같은 조작 을 제공 해 야 합 니 다.(후계 정 의 는 x 보다 크 고 가장 작은 수) 첫 번 째 줄 두 개 수 n, m 는 길이 n 의 질서 있 는 서열 과 m 개의 조작 두 번 째 줄 은 n ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.