你说我怎么这么菜呢?

T1:

考场上没看到下取整，同时把那个sigma看成了次数，以为要在mod phi(p)下算，这玩意能做？

然后果断爆零......

其实puts(2的逆元)+puts("1")有25分......

正解看官方题解吧。

那个鬼畜的容斥大概就是在n+1个断点中钦定k个断点，数字相对于剩下的m+1-k个集合的位置无关，所以对于这m+1-k个集合可以随意放置。

代码:

1 #include
      
        2 #include
       
         3 typedef long long int lli; 4 const int maxn=1e5+1e2,maxl=262145; 5 const int mod=998244353,g=3; 6  7 lli fac[maxn],inv[maxn]; 8 lli lft[maxl],rit[maxl],tar[maxl]; 9 lli ans;10 int n,m;11 12 inline lli fastpow(lli base,int tim) {13     lli ret = 1;14     while( tim ) {15         if( tim & 1 ) ret = ret * base % mod;16         if( tim >>= 1 ) base = base * base % mod;17     }18     return ret;19 }20 inline void NTT(lli* dst,int n,int ope=1) {21     for(int i=0,j=0;i
        
         >1;(j^=t)
         
          >=1);24     }25     for(int len=2;len<=n;len<<=1) {26         const int h = len >> 1;27         lli per = fastpow(g,mod/len);28         if( !~ope ) per = fastpow(per,mod-2);29         for(int st=0;st
         
        
       
      

T2:

n方暴力很好写吧......

考虑二维平面，一条路径相当于让两边花式取min，然后不会写了。

写了一个大力random_shuffle也没有骗到subtask2的分......

正解是分治，考虑我们把这个东西划分成多个三角形，然后枚举中间的一条边，分别计算经过这条边两个点的询问的代价并递归计算两边询问的代价。

因为显然两个点分别在这条边两边的询问的最有路径至少过这条边两个端点中的一个......

然而这种分治可能把一个求解区间变成上下两个不连通的联通快......所以在更新时需要特判一下-1，在递归边界也要特判......

话说第一次写这个我还写傻了，写了8kb代码死活调不出来......后来重构了才成功AC。

25分暴力代码:

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #define debug cout 8 using namespace std; 9 const int maxn=1e5+1e2;10 11 struct Node {12 int y,id;13 };14 struct QNode {15 int siz,id;16 friend bool operator < (const QNode &a,const QNode &b) {17 return a.siz < b.siz;18 }19 };20 vector
            
              qs[maxn];21 priority_queue
             
               pq;22 queue
              
                q;23 vector
               
                 vec[maxn];24 int siz[maxn],dis[maxn],ans[maxn];25 int n,m;26 27 inline void bfs(int st) {28 memset(dis,-1,sizeof(int)*n) , dis[st] = 0;29 q.push(st);30 while( q.size() ) {31 const int pos = q.front(); q.pop();32 for(unsigned j=0;j
               
              
             
            
           
          
         
        
       
      

正解代码:

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #define debug cout 9 using namespace std; 10 const int maxn=1e5+1e2; 11 const int inf=0x3f3f3f3f; 12 13 struct Query { 14 int a,b,id; 15 }; 16 int s[maxn],t[maxn<<2],nxt[maxn<<2]; 17 int disx[maxn],disy[maxn],id[maxn],pt[maxn],iid,cnt; 18 vector
             
               qs; 19 vector
              
                ps; 20 int ans[maxn]; 21 22 inline void addedge(int from,int to) { 23 static int cnt = 0; 24 t[++cnt] = to , nxt[cnt] = s[from] , s[from] = cnt; 25 swap(from,to); 26 t[++cnt] = to , nxt[cnt] = s[from] , s[from] = cnt; 27 } 28 29 inline void bfs(int st,int* dis) { 30 queue
               
                 q; dis[st] = 0 , q.push(st); 31 while( q.size() ) { 32 const int pos = q.front(); q.pop(); 33 for(int at=s[pos];at;at=nxt[at]) 34 if( !~dis[t[at]] && id[t[at]] == id[pos] ) 35 dis[t[at]] = dis[pos] + 1 , q.push(t[at]); 36 } 37 } 38 39 inline void solve(const vector
                
                  &ps,const vector
                 
                   &qs) { 40 if( !qs.size() ) return; 41 if( ps.size() <= 3 ) { 42 ++iid; 43 for(unsigned i=0;i
                  
                    pt[y] ) swap(x,y); 67 bfs(x,disx) , bfs(y,disy); 68 vector
                   
                     pl,pr; 69 vector
                    
                      ql,qr; 70 for(unsigned i=0;i
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      

写傻了的代码:

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
          
         
        
       
      

T3:

显然答案不能在区间不是单调不增的时候为len，否则为1。

n方暴力依然好写。

只有加的情况也很容易。

于是我考场上写了自调整分块trick过了40分......

但是在处理取min的时候存在问题，不能AC。

正解是线段树，然而我并不会jry线段树。

于是考虑乱搞，维护区间min，区间max，后面有一个更大的值的最小的umin，然后合并时讨论一下就好了。

两个标记的话让加法优于取min，因为我们能在min上进行加法修改。应用的时候先加法即可。

40分分块代码:

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #define debug cout  7 typedef long long int lli;  8 using namespace std;  9 const int maxn=1e5+1e2,maxb=319; 10 const lli inf=0x3f3f3f3f3f3f3f3fll; 11  12 int bel[maxn],st[maxb],ed[maxb]; 13 lli in[maxn],lazy_add[maxb],lazy_min[maxb],mxv[maxb],miv[maxb]; 14 bool flag[maxb]; 15 int n; 16  17 inline void block_add(int pos,int l,int r,lli t) { 18     l = max( l , st[pos] ) , r = min( r , ed[pos] ) , flag[pos] = 0; 19     for(int i=l;i<=r;i++) { 20         in[i] += t; 21         if( i != l ) flag[pos] |= ( in[i-1] < in[i] ); 22     } 23 } 24 inline void block_min(int pos,int l,int r,lli t) { 25     l = max( l , st[pos] ) , r = min( r , ed[pos] ) , flag[pos] = 0; 26     for(int i=l;i<=r;i++) { 27         in[i] = min( in[i] , t ); 28         if( i != l ) flag[pos] |= ( in[i-1] < in[i] ); 29     } 30 } 31 inline void rebuild_blk(int pos) { 32     miv[pos] = inf , mxv[pos] = 0 , flag[pos] = 0; 33     for(int i=st[pos];i<=ed[pos];i++) { 34         miv[pos] = min( miv[pos] , in[i] ) , 35         mxv[pos] = max( mxv[pos] , in[i] ) ; 36         if( i != st[pos] ) flag[pos] |= ( in[i-1] < in[i] ) ; 37     } 38 } 39 inline void push_lazy(int pos) { 40     int fail = 1; 41     if( lazy_add[pos] ) { 42         block_add(pos,st[pos],ed[pos],lazy_add[pos]); 43         lazy_add[pos] = 0 , fail = 0; 44     } 45     if( lazy_min[pos] < inf ) { 46         block_min(pos,st[pos],ed[pos],lazy_min[pos]); 47         lazy_min[pos] = inf , fail = 0; 48     } 49     if( !fail ) rebuild_blk(pos); 50 } 51 inline void fully_add(int pos,lli x) { 52     lazy_add[pos] += x , lazy_min[pos] += x , 53     miv[pos] += x , mxv[pos] += x; 54 } 55 inline void fully_min(int pos,lli x) { 56     lazy_min[pos] = min( miv[pos] , x ) , 57     miv[pos] = min( miv[pos] , x ) , 58     mxv[pos] = min( mxv[pos] , x ) ; 59 } 60 inline void partly_add(int pos,int l,int r,lli x) { 61     push_lazy(pos) , 62     block_add(pos,l,r,x) , 63     rebuild_blk(pos) ; 64 } 65 inline void partly_min(int pos,int l,int r,lli x) { 66     push_lazy(pos) , 67     block_min(pos,l,r,x) , 68     rebuild_blk(pos) ; 69 } 70 inline void update_add(int l,int r,lli x) { 71     if( bel[l] == bel[r] ) return partly_add(bel[l],l,r,x); 72     for(int i=bel[l]+1;i
          
         
        
       
      

正解代码:

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #define debug cout  6 typedef long long int lli;  7 using namespace std;  8 const int maxn=1e5+1e2;  9 const lli inf=0x3f3f3f3f3f3f3f3fll,lim=inf>>4; 10  11 struct Node { 12     lli miv,mxv,umiv,umxv; 13     friend Node operator + (const Node &a,const Node &b) { 14          Node ret = (Node){min(a.miv,b.miv),max(a.mxv,b.mxv),inf,-inf}; 15          if( a.miv < b.mxv ) ret.umiv = a.miv , ret.umxv = b.mxv; 16          if( a.umiv < ret.umiv ) ret.umiv = a.umiv , ret.mxv = max( a.umxv , b.mxv ); 17          if( b.umiv < ret.umiv ) ret.umiv = b.umiv , ret.umxv = b.umxv; 18          return ret; 19     } 20     inline void fill(const int &x) { 21         miv = mxv = x , umiv = inf , umxv = -inf; 22     } 23     inline void apply_add(const lli &x) { 24         miv +=x , mxv +=x , umiv += x , umxv += x; 25     } 26     inline void apply_min(const lli &x) { 27         miv = min( miv , x ) , mxv= min( mxv , x ); 28         if( umiv < x ) umxv = max( umxv , x ); 29         else umiv = inf , umxv = -inf; 30     } 31 }ns[maxn<<3]; 32  33 int in[maxn]; 34 int l[maxn<<3],r[maxn<<3],lson[maxn<<3],rson[maxn<<3],cnt; 35 lli lazy_add[maxn<<3],lazy_min[maxn<<3]; 36  37 inline void build(int pos,int ll,int rr) { 38     l[pos] = ll , r[pos] = rr; 39     if( ll == rr ) return ns[pos].fill(in[ll]); 40     const int mid = ( ll + rr ) >> 1; 41     build(lson[pos]=++cnt,ll,mid) , build(rson[pos]=++cnt,mid+1,rr); 42     ns[pos] = ns[lson[pos]] + ns[rson[pos]]; 43 } 44 inline void apply_add(int pos,const lli &x) { 45     lazy_add[pos] += x , lazy_min[pos] += x , 46     ns[pos].apply_add(x); 47 } 48 inline void apply_min(int pos,const lli &x) { 49     lazy_min[pos] = min( lazy_min[pos] , x ) , 50     ns[pos].apply_min(x); 51 } 52 inline void push(int pos) { 53     if( lazy_add[pos] ) { 54         apply_add(lson[pos],lazy_add[pos]) , apply_add(rson[pos],lazy_add[pos]) , 55         lazy_add[pos] = 0; 56     } 57     if( lazy_min[pos] < lim ) { 58         apply_min(lson[pos],lazy_min[pos]) , apply_min(rson[pos],lazy_min[pos]) , 59         lazy_min[pos] = inf; 60     } 61 } 62 inline void update_add(int pos,int ll,int rr,const lli &x) { 63     if( rr < l[pos] || r[pos] < ll ) return; 64     if( ll <= l[pos] && r[pos] <= rr ) return apply_add(pos,x); 65     push(pos); 66     update_add(lson[pos],ll,rr,x) , update_add(rson[pos],ll,rr,x) , 67     ns[pos] = ns[lson[pos]] + ns[rson[pos]] ; 68 } 69 inline void update_min(int pos,int ll,int rr,const lli &x) { 70     if( rr < l[pos] || r[pos] < ll ) return; 71     if( ll <= l[pos] && r[pos] <= rr ) return apply_min(pos,x); 72     push(pos); 73     update_min(lson[pos],ll,rr,x) , update_min(rson[pos],ll,rr,x) , 74     ns[pos] = ns[lson[pos]] + ns[rson[pos]]; 75 } 76 inline Node query(int pos,int ll,int rr) { 77     if( ll <= l[pos] && r[pos] <= rr ) return ns[pos]; 78     push(pos); 79     const int mid = ( l[pos] + r[pos] ) >> 1; 80     if( rr <= mid ) return query(lson[pos],ll,rr); 81     if( ll > mid ) return query(rson[pos],ll,rr); 82     const Node ql = query(lson[pos],ll,rr) , qr = query(rson[pos],ll,rr); 83     return ql + qr; 84 } 85  86 int main() { 87     static int n,m; 88     scanf("%d%d",&n,&m) , memset(lazy_min,0x3f,sizeof(lazy_min)); 89     for(int i=1;i<=n;i++) scanf("%d",in+i); 90     build(cnt=1,1,n); 91     for(int i=1,o,l,r,x;i<=m;i++) { 92         scanf("%d%d%d",&o,&l,&r); 93         if( o == 3 ) { 94             Node ans = query(1,l,r); 95             printf("%d\n",ans.umiv