vijos 1459 treap
제목: 중국어
사고: n ^ 2 의 예비 처 리 를 직접 하면 됩 니 다. 그리고 logn 이 있 습 니 다. n 이 비교적 작 으 면 통과 할 수 있 습 니 다.
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3fll;
const int maxn=1010;
ll A[maxn],ans[maxn][maxn];
inline int getint(){
int res=0;
char c=getchar();
bool mi=false;
while(c'9') mi=(c=='-'),c=getchar();
while('0'<=c && c<='9') res=res*10+c-'0',c=getchar();
return mi ? -res : res;
}
inline ll getll(){
ll res=0;
char c=getchar();
bool mi=false;
while(c'9') mi=(c=='-'),c=getchar();
while('0'<=c && c<='9') res=res*10+c-'0',c=getchar();
return mi ? -res : res;
}
struct Node{
Node *ch[2];
int r,s;
ll v,sum;
Node(ll v):v(v){ch[0]=ch[1]=NULL;r=rand();s=1;sum=0;}
int cmp(ll x){
if(x==v) return -1;
return xs,sum+=ch[0]->sum;
if(ch[1]!=NULL) s+=ch[1]->s,sum+=ch[1]->sum;
}
};
Node *root;
void Rotate(Node* &o,int d){
Node* k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;
o->maintain();k->maintain();o=k;
}
void Insert(Node* &o,ll x){
if(o==NULL) o=new Node(x);
else{
int d=xv)? 0:1;
Insert(o->ch[d],x);
if(o->ch[d]->r>o->r) Rotate(o,d^1);
}
o->maintain();
}
ll Kth(Node* o,int k,int op,ll pp){
int s=(o->ch[0]==NULL?0:o->ch[0]->s);
ll lll=0,qqq=0;
if(o->ch[1]!=NULL) lll=o->ch[1]->sum;
if(o->ch[0]!=NULL) qqq=o->ch[0]->sum;
if(kch[0],k,op,pp+lll+o->v);
else if(k>s+1) return Kth(o->ch[1],k-(s+1),op,pp-qqq-o->v);
else{
ll tmp1=pp,tmp2=0;
if(o->ch[1]!=NULL) tmp1+=o->ch[1]->sum;
if(o->ch[0]!=NULL) tmp2=o->ch[0]->sum;
if(op==1) return tmp1-(o->v)-tmp2;
else return tmp1-tmp2;
}
}
int main(){
int n,m,x,y,op;
while(scanf("%d%d",&n,&m)!=-1){
for(int i=1;i<=n;i++) A[i]=getll();
memset(ans,0,sizeof(ans));
ll fans=0;
for(int i=1;i<=n;i++){
root=NULL;
for(int j=i;j<=n;j++){
Insert(root,A[j]);
if((j-i+1)%2==0) op=1;
else op=0;
ans[i][j]=Kth(root,(j-i)/2+1,op,0);
}
}
for(int i=0;i
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu 1233 절 대 컴퓨터 대학원 재시험모 성에 서 마을 의 교통 상황 을 조사 하여 얻 은 통계표 에는 임의의 두 마을 간 의 거리 가 열거 되 어 있다.성 정부의 '원활 한 공사' 목 표 는 성 전체의 어느 두 마을 간 에 도 도로 교통 을 실현 할 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.