然而并没有通过 100 分，在实际测试中因为数据出现自环掉了 10 分。

考虑有一个显而易见的平方做法是，直接枚举起点，然后出边必须唯一，否则无解。

有一个显而易见的剪枝是，如果一个起点不可行，那么他经过的所有点全都不可行。

有一个显而易见的转化是，最终答案大概会是一个环作循环移位，然后这个很简单。

然后你写出来发现挂了。

上面这张图有两个方案，一个是 1 8 7 2 10 9 5 3 4 6，另一个是 4 6 8 7 2 10 9 5 3 1，但是容易发现这个只会在开头和结尾错开最多一次，所以我们可以找两次环。

然后问题就是怎么找环，考虑剪枝，如果一个点被搜到过，并且搜到他的点寄了，那就寄了。

然后你提交哇居然直接通过，qoj 也直接通过，真实太牛了！！！

实际上也很好卡，但是你随一下排列就卡不掉了，真实太牛了！！！

考虑最大子段和，我们考虑有一个经典的 dp，就是 $dp_i=\max(dp_{i-1},0)+a_i$。

然后容易发现在操作的过程中的选择支只有前面那两项。

我们发现把取第一项和第二项的缩起来可以得到几个连续段，这些连续段的开头的选择必然是 0。

我们容易发现，对一个数 $a_i$ 操作 $-1$，相当于给 $dp_i$ 操作 $-1$，然后再来考虑这个操作的影响，容易发现，这个操作的影响是和他在同一个连续段的他后面的点。

也就是说如果我要操作，那就一定操作连续段开头，这一定不劣于操作连续段中间。

然后考虑一直减，直到什么时候我要停下呢，存在一个 dp 的取值来到 0，选择支改变的时候，我就要把这个子段裂开。

我们先不管怎么裂开，考虑时间复杂度对不对。

考虑我们什么时候会停下，要么是有一段可以和我们一起操作，要么是有一段被减成 0 然后拉去枪毙，考虑随便分析一下势能，总共的操作次数是 $O(n)$ 的。

然后怎么分裂呢？聪明地同学就要说了，对，启发式分裂！然后你就可以开始写十几 k 代码再把头发抓没了。

考虑先不管他不同子段间的删除顺序，他每次分裂一定都是这个段中 dp 的最小值，然后以这个为中心裂成两半，有点像笛卡尔树，所以我们预先建立笛卡尔树，然后每次要分裂了就把这个点传给他的两个儿子。

然后就做完了！但是细节有点多！

1. 考虑虽然我这个点不产生贡献但是他仍然还在 dp 里，具体来说

28 -20090515 20090627

上面这个例子中，-20090515 虽然很小但是他还是会靠着 $28$，但他没办法对后面的 20090627 造成贡献，因为他太小了。

而且每次访问的可行 $dp_{i-1}$ 也是编号不对，这个下标差就很恶心，同时我们做的删除贡献操作并没有维护这个点后续的贡献，所以我们考虑维护状态在 $[lt,rt)$ 里的 dp，然后在笛卡尔树的时候考虑如果分裂的过程中没有右儿子，实际上也就是右边的节点是 $rt$，这个时候我才能够把他扔进一个点的集合里；如果没有左儿子，也就是这个即将被删除的点没有点可以依靠，那把这个点扔进去就好了。

1. 标记下传

考虑我们肯定不能真的维护 dp，但是我们可以转而维护 dp 的标记，然后在笛卡尔树上直接下传就……还不可以！

考虑对于一个点他成为单点的时候只有真正贡献给他自己的点才有用，所以还要对于每个点记录他被操作了多少次。

然后可能就没有了，就是注意取模，这个题取模特别猥琐，就是，但是反正你那个式子打一百万个括号每个项单独模一遍也差不多了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,K;
int A[200005];
int dp[200005];
int tot;
struct qry{
   int lt,rt;
}B[200005];
int top;
int stk[200005];
int ch[200005][2];
int root[200005];
int upd[200005];
int L[200005],R[200005];
int tag[200005];
struct node{
   int id,val;
   bool friend operator < (const node &a,const node &b){
      return a.val>b.val;
   }
};
priority_queue<node> Q,P,T;
void build(int lt,int rt,int id){
   top=0;
   for(int i=lt;i<=rt;i++){
      int lst=0;
      while(top&&dp[stk[top]]>dp[i]){
         lst=stk[top];
         top--;
      }
      ch[i][0]=lst;
      if(!top){
         root[id]=i;
      }
      else{
         ch[stk[top]][1]=i;
      }
      stk[++top]=i;
   }
   return;
}
int siz[200005];
void getsiz(int cur,int lt,int rt){
   L[cur]=lt,R[cur]=rt;
   siz[cur]=dp[lt];
   if(lt>=rt){
      return;
   }
   if(ch[cur][0]){
      getsiz(ch[cur][0],lt,cur-1);
      siz[cur]=max(siz[cur],siz[ch[cur][0]]);
   }
   if(ch[cur][1]){
      getsiz(ch[cur][1],cur+1,rt);
      siz[cur]=max(siz[cur],siz[ch[cur][1]]);
   }
   return;
}
signed main(){
   // freopen("seg.in","r",stdin);
   // freopen("seg.out","w",stdout);
   scanf("%lld",&n);
   for(int i=1;i<=n;i++){
      scanf("%lld",&A[i]);
      L[i]=R[i]=0;
   }
   scanf("%lld",&K);
   for(int i=1;i<=n;i++){
      dp[i]=max(dp[i-1],0ll)+A[i];
      if(dp[i-1]<=0){
         tot++;
         B[tot].lt=i,B[tot].rt=i;
      }
      else{
         B[tot].rt++;
      }
   }
   if(dp[n]>0){
      A[++n]=-1e18;
      dp[n]=max(dp[n-1],0ll)+A[n];
      B[tot].rt=n;
   }
   for(int i=1;i<=tot;i++){
      int lt=B[i].lt,rt=B[i].rt;
      if(lt<rt){
         build(lt,rt-1,i);
      }
   }
   int ans=-1e18;
   for(int i=1;i<=n;i++){
      ans=max(ans,dp[i]);
   }
   int num=0;
   for(int i=1;i<=tot;i++){
      if(B[i].lt<B[i].rt){
         getsiz(root[i],B[i].lt,B[i].rt-1);
         if(siz[root[i]]==ans){
            num++;
            Q.push(node{root[i],dp[root[i]]});
         }
         else{
            P.push(node{root[i],-siz[root[i]]});
         }
      }
      else{
         if(dp[B[i].lt]==ans){
            num++;
         }
         else{
            T.push(node{B[i].lt,-A[B[i].lt]});
         }
      }
   }
   int lst=0;
   int delta=0;
   while(K>=num){
      int need=K/num;
      if(Q.size()){
         need=min(need,Q.top().val-delta);
      }
      if(P.size()){
         need=min(need,ans+P.top().val);
      }
      if(T.size()){
         need=min(need,ans+T.top().val);
      }
      // printf("%lld\n",need);
      K-=num*need;
      delta+=need;
      lst+=((num)*((ans+(ans-need+1))%998244353)%998244353*(need%998244353)%998244353*((998244353+1)/2)%998244353)%998244353-need%998244353+998244353;
      lst=(lst%998244353+998244353)%998244353;
      ans-=need;
      while(Q.size()&&Q.top().val-delta==0){
         node tmp=Q.top();
         Q.pop();
         num--;
         int lson=ch[tmp.id][0];
         int rson=ch[tmp.id][1];
         int val=dp[tmp.id]+tag[tmp.id];
         assert(val>=0);
         int now=tmp.val-delta;
         int dt=now-val;
         tag[tmp.id]+=dt;
         upd[L[tmp.id]]+=dt;
         if(lson){
            tag[lson]+=tag[tmp.id];
            if(siz[lson]+tag[lson]==ans){
               num++;
               Q.push(node{lson,dp[lson]+tag[lson]+delta});
            }
            else{
               P.push(node{lson,-(siz[lson]+tag[lson])});
            }
         }
         else{
            T.push(node{tmp.id,-(A[tmp.id]+upd[tmp.id])});
         }
         if(rson){
            tag[rson]+=tag[tmp.id];
            if(siz[rson]+tag[rson]==ans){
               num++;
               Q.push(node{rson,dp[rson]+tag[rson]+delta});
            }
            else{
               P.push(node{rson,-(siz[rson]+tag[rson])});
            }
         }
         else{
            T.push(node{tmp.id+1,-(A[tmp.id+1]+upd[tmp.id+1])});
         }
      }
      while(P.size()&&(-P.top().val==ans)){
         node tmp=P.top();
         P.pop();
         Q.push(node{tmp.id,dp[tmp.id]+tag[tmp.id]+delta});
         num++;
      }
      while(T.size()&&(-T.top().val==ans)){
         num++;
         T.pop();
      }
   }
   printf("%lld\n",((lst+ans%998244353*K%998244353)%998244353+998244353)%998244353);
   return 0;
}

如果你通过了一个测试点，你可以获得 10 分，否则单个测试点内就会按照 100 分来算部分分，然后就可以获得 900 分。

又注意到 uoj 判有没有过题不是按测试点来判而是有没有达到 100 分，所以就可以通过打表 q 比较小的两个测试点来卡出 100 分……