二分答案

检验的时候，从前往后枚举，如果发现某个位置的防御力<二分的值，那么新加的位置肯定是越靠后越好

差分即可

 

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define N 500001typedef long long LL;int n,r; LL k;LL sum[N];LL cf[N];template
         
          void read(T &x){    x=0; char c=getchar();    while(!isdigit(c)) c=getchar();    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}bool check(LL x){    LL rest=k,need;    LL add=0;    memset(cf,0,sizeof(cf));    for(int i=1;i<=n;++i)    {        add+=cf[i];        if(sum[i]+add
          
           >1; if(check(mid)) ans=mid,l=mid+1; else r=mid-1; } cout<