题解：P14522 【MX-S11-T3】空之碎物

· · 题解

（该解法最终时间消耗为 1.06s , 最大单组数据 186ms )

题意：

将一个区间 [l,r] 内的数用二进制不退位减法合并为一个数，使最终得到的数最大，将该值记为 f([l,r]) ，求各个区间所有最大值的总和

解法：

(本文中，w 为 [1,n] 最大值的二进制位数，计算复杂度时认为 w=25 ，“减”指题目中定义的运算)

初步思想（复杂度 O(wn^5) ) :

一种显而易见的贪心：让一个数作为最终轮被“减”数不变，另一个数“减”去其他区间内的数，最终用最终轮被“减”数减去这个数，更新该区间的最大值。

这种做法中，需要枚举每个区间，并在区间内枚举最终轮被“减”数和“减”数，且每次需要做 nw 次运算，最终复杂度 O(wn^5) ，显然无法通过本题

运算小优化（复杂度 O(n^5) ) ：

“减”运算实质为对每一位取

a&(!b)

所以我们可以直接这样做运算

此时复杂度为 O(n^5) ，显然仍然无法通过

对长区间的思考（复杂度 O(nw^3+n^2) ) :

我们发现，题目中共有 n^2 段区间，显然，最终解法不可能需要枚举每一个区间

我们考虑一个长区间，直觉告诉我们，最终可以使最终轮“减”数变为 0 ，考虑证明这一点。

我们考虑一个数在什么情况下不会变成 0 ，我们发现，当其在有一位 1 是在所有除最终轮被“减”数以外的数中独有时，其不会消去这一位 1 。

显然，每一位 1 最多只能被区间内一个数独有。（独有的概念不考虑最终轮被“减”数中是否有这个数字）

按题目范围，数最多有 25 位，也就是钦定最终轮被“减”数后最多有 25 个数做最终轮“减”数不会变为 0 ，再算上最终轮被“减”数，最多有 26 个数。

因此，r-l+1>26 的区间，必有选法使最终轮”减“数变为 0 ，即答案为区间最大值。

所以，我们两层循环遍历区间，计算区间最值和，复杂度为 O(n^2) 。

为方便实现，我们直接计算所有区间的区间最值和，并在枚举 r-l+1<=26 的区间时减去其中的区间最值。

考虑用同样的思想思考 r-l+1<=26 的区间的答案，我们想到，应该尽可能让最终轮“减”数独有位中与最终轮被“减”数共有的位的 1 总值（每位的 1 根据所在位有不同实际权，即其所在位的位值）尽量小。

思考什么样的位是最终轮“减”数独有且与最终轮被“减”数共有的，显然，当一个位的 1 在区间内共有两个，且在区间内最终轮被“减”数中存在时，这样的位是最终轮“减”数独有且与最终轮被“减”数共有的。

一个位在区间内的出现个数可以使用前缀和维护，预处理复杂度 O(nw) ，单次计算复杂度 O(w) ，每次枚举区间时计算区间内各个位的个数，需要处理 nw 个区间，总复杂度 O(nw^2)

然后我们对于每个 r-l+1<=26 区间，枚举其最终轮被“减”数，并根据上述结论进行可能独有位计算（计算每一位是否存在一个数独有且与最终轮被“减”数共有，时间消耗为 O(w) )。因为独有位是独有的二进制位的集合，所以可以用一个数保存独有位权值和。

区间个数 nw ，每个区间枚举 O(w) 个最终轮被“减”数，进行 w 次运算统计，该部分复杂度为 O(nw^3) 。

然后枚举最终轮“减”数，我们只需要将其与独有位权值和取与运算，就可以得到其独有位中与最终轮被“减”数共有的位的 1 总值。然后我们用最终轮被“减”数减去这个数，更新该区间内的答案。

区间个数 nw ，每个区间枚举 O(w) 个最终轮被“减”数，枚举 O(w) 个最终轮“减”数，该部分复杂度为 O(nw^3) 。

然后我们使 sum 减去区间内最大值（原因见上文区间最值和部分），再加上区间内的答案。

综上，该做法复杂度为 O(nw^3+n^2) ，仍然无法通过，我们考虑对两个部分分别进行优化。

最终优化（复杂度 O(nw^2) )：
区间最值和部分，单调栈统计贡献（该部分复杂度 O(n) ) :

暴力维护区间最值和不可行，我们考虑每个位置的贡献。

显然，每个位置在横跨该位置，且区间内的值不大于该位置的值时是区间内的最大值。

考虑使用单调栈维护位置 i 最靠左的 l_i 使得 [l_i,i] 的数小于 i 和位置 i 最靠右的 r_i 使得 [i,r_i] 的数不大于 i （为防止重复元素的贡献被多次或不计算，需要一边小于一边不大于，在这里令左边小于右边不大于），然后该位置的贡献即为 a[i] \times (i-l_i+1) \times (r_i-i+1) ，计算各位置贡献和，即为区间最值和。该做法仅需遍历三次数组，复杂度为 O(n) 。

枚举部分，使用 set 辅助剪枝（该部分复杂度 O(nw^2) ）：

显然，当一个数作为最终轮被“减”数时，其更新的答案不可能大于这个数本身。

因此当一个数小于等于当前答案时，无需再考虑其为最终轮“减”数的情况。

同时，当区间已经有两个数之后，向一个区间里加数不会使答案更小（直接交给最终轮“减”数去减就行）

所以，我们对同一起点的区间统一处理，将之前的答案保存下来，用于后续更新。

然后用 set 保存区间内每一个可能是最终轮被“减”数的位置，按初值从大到小依次遍历，当发现当前选的值小于等于目前答案时，从当前迭代器开始删除，不再遍历以后的部分。

这样，我们对每个起点的区间选择最终轮被“减”数的次数就是 O(w) 的。（大概原因：当区间内的数差比较大时，小的会被淘汰，差比较小时，答案会接近最值，较小的会被淘汰。但是我不知道怎么证明这个在最坏数据下也是线性。）

起点个数 n ，每个起点的区间选择最终轮被“减”数的次数 O(w) ，每次处理 O(w) ，最终复杂度 O(nw^2) 。

代码：

#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
namespace KitoTaisu{//快读 
    char *p1,*p2,buf[32769];
    #define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,32767,stdin),p1==p2)?EOF:*p1++)
    int read(){
        int x=0,f=1;
        char ch=nc();
        while(ch<48||ch>57){
            if(ch=='-')f=-1;
            ch=nc();
        }
        while(47<ch&&ch<58){
            x=x*10+(ch^48);
            ch=nc();
        }
        return x*f;
    }
    int readstr(char* str){
        int len=0;
        char ch=nc();
        while(ch<37||ch>110){
            ch=nc();
        }
        while(36<ch&&ch<111){
            str[len++]=ch;
            ch=nc();
        }
        str[len]=0;
        return len;
    }
}
using KitoTaisu::read;
using KitoTaisu::readstr;
struct Nephren{
    int id,val;
    bool operator <(const Nephren a)const{
        return val>a.val;
    }
};
#define si set<Nephren>::iterator
#define md 998244353
set<Nephren> pss;
int n,Max,mx,ztn,zt[27],tmp[27],a[200002],pre[200002][27];
long long sum;//善用long long使常数不大的同时能保存足够大的数 
//debug的时候以为这有问题最终没用这个函数 
void menus(int* mnd,int* mns,int* ans){//求区间内各位的出现次数  
    for(int i=0;i<25;++i){
        ans[i]=mnd[i]-mns[i]; 
    }
} 
int len,kl[200002],kr[200002],stk[200002];
int main(){
    n=read();
    for(int i=1;i<=n;++i){
        a[i]=read();
        for(int j=0;j<25;++j){
            if(a[i]&(1<<j)){
                pre[i][j]=pre[i-1][j]+1;//前缀和预处理区间内各位的出现次数 
            }
            else pre[i][j]=pre[i-1][j];
        }
    }
    for(int i=1;i<=n;++i){
        while(len&&a[stk[len]]<=a[i]){ //单调栈维护点贡献可达的最右端 
            kr[stk[len]]=i-1;
            len--;
        }
        stk[++len]=i;
    }
    while(len){
        kr[stk[len]]=n;
        len--;
    }
    for(int i=n;i;--i){
        while(len&&a[stk[len]]<a[i]){//单调栈维护点贡献可达的最左端，注意要单边取等，避免相等时出现问题 
            kl[stk[len]]=i+1;
            len--;
        }
        stk[++len]=i;
    }
    while(len){
        kl[stk[len]]=1;
        len--;
    }
    for(int i=1;i<=n;i++){
        sum+=(long long)(a[i])*(i-kl[i]+1)%md*(kr[i]-i+1)%md;//计算区间最值和 
        sum%=md;
    }
//  for(int i=1;i<=n;i++){//O(n^2)的区间最值和 
//      mx=0;
//      for(int j=i;j<=n;j++){
//          mx=max(mx,a[j]);
//          sum+=mx;
//      }
//  }
    for(int i=1;i<n;++i){
        sum+=(Max=max(a[i]-(a[i]&a[i+1]),a[i+1]-(a[i]&a[i+1])))-(mx=max(a[i],a[i+1]));//特判长度为2的区间，并计算起点枚举初值
        // a[i]-(a[i]&a[i+1]) 是二进制不退位减法的另一种O（1）实现 
        sum=(sum+md)%md;//只在这里取余数，降低常数 
        pss.clear();
        if(a[i]>Max)pss.insert({i,a[i]});
        if(a[i+1]>Max)pss.insert({i+1,a[i+1]});
        //set初始情况 
        for(int j=2,k=i+2;j<27&&k<=n;++j,++k){
            if(a[k]>Max){
                pss.insert({k,a[k]});//加入可能的最终轮被“减”数 
            }
            si itl=pss.begin(),itr=pss.end();
            for(int p=0;p<25;++p){
                zt[p]=pre[k][p]-pre[i-1][p];//求出现次数 
            }
            for(si it=itl;it!=itr;++it){
                if((it->val)<=Max){
                    pss.erase(it,itr);//将不再可能是该起点最终轮被“减”数的数删去 
                    break;
                }
                ztn=0;
                for(int p=0;p<25;++p){
                    if(((it->val)&(1<<p))&&zt[p]==2)ztn+=(1<<p);//权值和计算 
                }
                for(int p=0;p<=j;++p){
                    if(i+p==(it->id))continue;//最终轮两个数不能是同一个 
                    tmp[p]=a[i+p]&ztn;//计算最终轮“减”数最终实际值 
                    Max=max(Max,(it->val)-tmp[p]);//更新答案 
                }
            }
            mx=max(mx,a[k]);
            sum+=Max-mx+md;//区间最值和中计算了所有区间的最值，在这里减去 
        }
    }
    printf("%lld",sum);
    return 0;
}