codeforces 278Div1 B题

痛定思痛。 2021-10-23 07:23 253阅读 0赞

虚拟参赛的时候没想到是线段树，看到很多人都过了，也蛮着急的。

首先用二分+线段树的方法更新DP\[i\]：它表示以A\[i\]为结尾可以最前到哪个位置；

再用线段树计算ans\[i\]：它表示当前i个A元素可以最少分成多少个pieces，ans\[i\]=1+min(ans\[j\])，dp\[i\]-1<=j<=i-L。

over.

16 #define N 100000+5
     17 
     18 int a[N],dp[N],Ans[N];
     19 struct segment {
     20     int l,r;
     21     int Min,Max,ans;
     22 } seg[4*N];
     23 
     24 struct diff {
     25     int Max,Min;
     26     diff(int x=0,int n=0):Max(x),Min(n) {}
     27 };
     28 
     29 void build(int p,int l,int r)
     30 {
     31     seg[p].l=l, seg[p].r=r, seg[p].ans=-1;;
     32     if (l==r) {
     33         seg[p].Min = seg[p].Max = a[l];
     34         return;
     35     }
     36     build(p<<1,l,(l+r)>>1);
     37     build((p<<1)+1,((l+r)>>1)+1,r);
     38 
     39     seg[p].Min = min(seg[p<<1].Min, seg[(p<<1)+1].Min),
     40     seg[p].Max = max(seg[p<<1].Max, seg[(p<<1)+1].Max);
     41 }
     42 
     43 diff query1(int p,int l,int r)
     44 {
     45     if (l<=seg[p].l && seg[p].r<=r) {
     46         return diff(seg[p].Max,seg[p].Min);
     47     }
     48 
     49     diff t1,t2;
     50     bool f1=false, f2=false;
     51     if (seg[p<<1].r>=l)
     52         f1=true, t1=query1(p<<1,l,r);
     53     if (seg[(p<<1)+1].l<=r)
     54         f2=true, t2=query1((p<<1)+1,l,r);
     55 
     56     if (f1) {
     57         if (f2)
     58             return diff(max(t1.Max,t2.Max), min(t1.Min,t2.Min));
     59         else
     60             return t1;
     61     }
     62     else
     63         if (f2)
     64             return t2;
     65     return diff(0,0);
     66 }
     67 
     68 int query2(int p,int l,int r)
     69 {
     70     if (l<=seg[p].l && seg[p].r<=r) {
     71         return seg[p].ans;
     72     }
     73 
     74     int t1=-1,t2=-1;
     75     if (seg[p<<1].r>=l)
     76         t1=query2(p<<1,l,r);
     77     if (seg[(p<<1)+1].l<=r)
     78         t2=query2((p<<1)+1,l,r);
     79 
     80     if (t1==-1) {
     81         return t2;
     82     }
     83     else {
     84         if (t2==-1)
     85             return t1;
     86         else return min(t1,t2);
     87     }
     88 
     89 }
     90 
     91 void add(int p,int i,int newans)
     92 {
     93     if (seg[p].l==seg[p].r) {
     94         seg[p].ans=newans;
     95         return;
     96     }
     97 
     98     if (i<=seg[p<<1].r)
     99         add(p<<1,i,newans);
    100     else
    101         add((p<<1)+1,i,newans);
    102 
    103     if (seg[p<<1].ans==-1) {
    104         seg[p].ans = seg[(p<<1)+1].ans;
    105     }
    106     else {
    107         if (seg[(p<<1)+1].ans==-1)
    108             seg[p].ans=seg[p<<1].ans;
    109         else
    110             seg[p].ans=min(seg[p<<1].ans,seg[(p<<1)+1].ans);
    111     }
    112 }
    113 
    114 int main()
    115 {
    116     //freopen("b.txt","r",stdin);
    117 
    118     int n,s,l;
    119     cin>>n>>s>>l;
    120     for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    121     build(1,1,n);
    122     for (int i=1;i<=n;i++) {
    123         int L=1,R=i-1;
    124         dp[i]=i;
    125         while (L<=R) {
    126             int mid = (L+R)>>1;
    127             diff tmp = query1(1,mid,i);
    128             if (tmp.Max-tmp.Min<=s) {
    129                 R=mid-1;
    130                 dp[i]=mid;
    131             }
    132             else {
    133                 L=mid+1;
    134             }
    135         }
    136     }
    137 
    138 
    139     for (int i=1;i<=n;i++) {
    140         if (i<l) {
    141             Ans[i]=-1;
    142             continue;
    143         }
    144         int tmp=-1;
    145         if (i-l>0 && dp[i]-1<=i-l)
    146             tmp=query2(1,max(1,dp[i]-1),i-l);
    147         if (dp[i]==1) tmp=0;
    148 
    149         if (tmp==-1)
    150             Ans[i]=-1;
    151         else
    152             Ans[i]=tmp+1, add(1,i,Ans[i]);
    153     }
    154     cout<<Ans[n]<<endl;
    155 
    156     return 0;
    157 }

转载于:https://www.cnblogs.com/nuaalida/p/4129407.html