Poj 2182-Lost Cows（Treap||树状数组+二分答案）

```#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define maxn 8005
#define _ll __int64
#define ll long long
#define INF 0x3f3f3f3f
#define Mod 1<<40+10
#define pp pair<int,int>
#define ull unsigned long long
using namespace std;
int n,ans[maxn];
struct node{
node *ch[2];
int r,v,s;
node (){}
node (int v){ch[0]=NULL;ch[1]=NULL;r=rand();this->v=v;s=1;}
bool operator <(const node& c)const{
return r<c.r;
}
int cmp(int x)const {
if(x==v)return -1;
return x<v?0:1;
}
void maintain(){
s=1;
if(ch[0]!=NULL)s+=ch[0]->s;
if(ch[1]!=NULL)s+=ch[1]->s;
}
};
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,int x)
{
if(o==NULL) o=new node(x);
else{
int d=o->cmp(x);
insert(o->ch[d],x);
if(o->ch[d]->r>o->r)rotate(o,d^1);
}
o->maintain();
}
void remove(node* &o,int x)
{
int d=o->cmp(x);
if(d==-1){
node* u=o;
if(o->ch[0]!=NULL&&o->ch[1]!=NULL){
int d2=(o->ch[0]->r>o->ch[1]->r?1:0);
rotate(o,d2);remove(o->ch[d2],x);
}
else{
if(o->ch[0]==NULL)o=o->ch[1];
else o=o->ch[0];
delete u;
}
}
else
remove(o->ch[d],x);
if(o!=NULL) o->maintain();
}
bool find(node* o,int x)
{
while(o!=NULL)
{
int d=o->cmp(x);
if(d==-1)return 1;
else o=o->ch[d];
}
return 0;
}
int find_kth(node* o,int k)
{
if(o==NULL||k>o->s)return -1;
int s=(o->ch[0]==NULL?0:o->ch[0]->s);
if(k==s+1)return o->v;
else if(k<=s) return find_kth(o->ch[0],k);
else return find_kth(o->ch[1],k-s-1);
}

void solve()
{
node *root=NULL;
for(int i=1;i<=n;i++)
insert(root,i);
for(int i=0;i<n-1;i++)
scanf("%d",&ans[i]);
for(int i=n-2;i>=0;i--){
//cout<<"ans["<<i<<"]=="<<ans[i]<<endl;
ans[i]=find_kth(root,ans[i]+1);
//cout<<"ans["<<i<<"]=="<<ans[i]<<endl;
remove(root,ans[i]);
}
printf("%d\n",root->v);
for(int i=0;i<=n-2;i++)
printf("%d\n",ans[i]);
}
int main()
{
while(~scanf("%d",&n))
solve();
return 0;
}```

POJ 题目2481 Cows（树状数组）

Cows Time Limit: 3000MS   Memory Limit: 65536K Total Submissions: 13920   Accepted: 4607 Description Farmer John's cows have discovered that the clover growing along the ridge of the hill (which we can think of as a one-dimensional number line) in hi

POJ 2182 Lost Cows.(线段树）

~~~~ 数据太水,暴力无压力,不过还是用线段树写了下,表现了楼主对线段树的无限热爱之情. ~~~~ 题目连接:http://poj.org/problem?id=2182 大致题意;牛牛因XXXXXX原因乱序成一排,现已知每头牛前面有多少头牛比它的编号小(第一头牛前面没有当然就不列粗来了),求每头牛的编号. 思路:从后往前扫描,遇到a,则说明它是剩余序列的第a+1头牛. ~~~~ 暴力代码:(157ms) #include<cstdio> #include<algorithm>

poj 3321:Apple Tree（树状数组，提高题）

Apple Tree Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 18623   Accepted: 5629 Description There is an apple tree outside of kaka's house. Every autumn, a lot of apples will grow in the tree. Kaka likes apple very much, so he has been