Codeforces Round #271 (Div. 2)

Codeforces Round #271 (Div. 2)

E待填坑

  1 #include <iostream>
  2 #include <cstdio>
  3 #include 
  4 #include <cstring>
  5 #include <vector>
  6 using namespace std;
  7 const int maxn=1e5+10;
  8 int pre[maxn];//记录前一个点
  9 long long num[maxn];
 10 long long a[maxn];
 11 int cur;
 12 struct node
 13 {
 14     int maxcou;//以这个高度结尾的最大长度
 15     int pos;//以这个高度结尾的元素的位置
 16 }tree[maxn<<2];
 17 void build(int rt,int l,int r)
 18 {
 19     if(l==r)
 20     {
 21         tree[rt].maxcou=0;
 22         tree[rt].pos=0;
 23         return;
 24     }
 25     int mid=(l+r)>>1;
 26     build(rt<<1,l,mid);
 27     build(rt<<1|1,mid+1,r);
 28     tree[rt].maxcou=0;
 29     tree[rt].pos=0;
 30 }
 31 int Rfind ( long long x ) {
 32     int l = 1 , r = cur ;
 33     while ( l < r ) {
 34         int m = ( l + r ) / 2 ;
 35         if ( a[m] >= x ) r = m ;
 36         else l = m + 1 ;
 37     }
 38     return l ;
 39 }
 40  
 41 int Lfind ( long long x ) {
 42     int l = 1 , r = cur ;
 43     while ( l < r ) {
 44         int m = ( l + r + 1 ) / 2 ;
 45         if ( a[m] <= x ) l = m ;
 46         else r = m - 1 ;
 47     }
 48     return r ;
 49 }
 50 void update(int x,int v,int i,int rt,int l,int r)
 51 {
 52     if(l==r)
 53     {
 54         if(v>tree[rt].maxcou)
 55         {
 56             tree[rt].maxcou=v;
 57             tree[rt].pos=i;
 58         }
 59         return;
 60     }
 61     int mid=(l+r)>>1;
 62     if(x<=mid)
 63     update(x,v,i,rt<<1,l,mid);
 64     else
 65     update(x,v,i,rt<<1|1,mid+1,r);
 66     if(tree[rt<<1].maxcou>tree[rt<<1|1].maxcou)
 67     {
 68         tree[rt].maxcou=tree[rt<<1].maxcou;
 69         tree[rt].pos=tree[rt<<1].pos;
 70     }
 71     else
 72     {
 73         tree[rt].maxcou=tree[rt<<1|1].maxcou;
 74         tree[rt].pos=tree[rt<<1|1].pos;
 75     }
 76 }
 77 int maxcount,maxpos;
 78 void query(int L,int R,int rt,int l,int r)
 79 {
 80     if(L>R)
 81     return;
 82     if(L<=l&&R>=r)
 83     {
 84         if(tree[rt].maxcou>maxcount)
 85         {
 86             maxcount=tree[rt].maxcou;
 87             maxpos=tree[rt].pos;
 88         }
 89         return;
 90     }
 91     int mid=(l+r)>>1;
 92     if(L<=mid)
 93     query(L,R,rt<<1,l,mid);
 94     if(R>mid)
 95     query(L,R,rt<<1|1,mid+1,r);
 96 }
 97 void prin(int u)
 98 {
 99     if(pre[u]!=0)
100     {
101         prin(pre[u]);
102         printf("%d ",pre[u]);
103     }
104     return;
105 }
106 int main()
107 {
108     int n,k,ids=1,ans=1;
109     scanf("%d%d",&n,&k);
110     memset(pre,0,sizeof(pre));
111     for(int i=1;i<=n;i++)
112     {
113         scanf("%I64d",&num[i]);
114         a[i]=num[i];
115     }
116     sort(a+1,a+n+1);
117     cur=1;
118     for(int i=2;i<=n;i++)//离散化，以元素的个数来建树，每个叶子节点代表一个高度
119     if(a[i]!=a[cur])
120     {
121         a[++cur]=a[i];
122     }
123     build(1,1,cur);
124     update(Lfind(num[1]),1,1,1,1,cur);
125     pre[1]=0;
126     for(int i=2;i<=n;i++)
127     {
128         int L=Lfind(num[i]-k);//小于num[i]-k的最大位置
129         int R=Rfind(num[i]+k);//大于num[i]+k的最小位置
130         maxcount=0,maxpos=0;
131         if(a[L]+k<=num[i])
132         {
133             query(1,L,1,1,cur);
134         }
135         if(num[i]+k<=a[R])
136         {
137             query(R,cur,1,1,cur);
138         }
139         update(Lfind(num[i]),maxcount+1,i,1,1,cur);
140         pre[i]=maxpos;
141         if(maxcount+1>ans)
142         {
143             ans=maxcount+1;
144             ids=i;
145         }
146     }
147     printf("%d\n",ans);
148     prin(ids);
149     printf("%d\n",ids);
150     return 0;
151 }

F有一个很奇妙的查找方式