题解
本题有一定代码难度
对于需要区间最大值，可以反过来考虑，先预处理出每个数所能扩展的最大边界，也就是说，求出一个最大的区间，其最大值为这个数，单调栈 (mathcal O(n)) 求解
那么对于第一问，我们记录一个数组 (bit)，(bit_{i,j}) 表示前 (i) 个数二进制下第 (j) 位为 (1) 的有多少
对于每一个数，设其左边界为 (l_i)，右边界为 (r_i)，则我们将这个区间分成两部分 (l_i～i)，(i～r_i)，选取数少的枚举
枚举每一位，若这个数这一为不为 (1)，则贡献为 (r_i-i+1-(bit_{r_i,j}-bit_{i-1,j}))，为 (0) 同理。
那么对于第二问，我们可以建一颗 (01trie)。
个人认为，可持久化 (01trie) 就相当于 (01trie) 前缀和，可以方便得求区间值
所以，我们这一问求得就是对于一个在 (num_j,jin [l_i,i]) 有多少 (k) 满足 ({num_j};;xor;;{num_k} > num_i)，(01trie) 求解即可
Code:
#include<bits/stdc++.h>
#define ri register signed
#define p(i) ++i
using namespace std;
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++
template<typename T>inline void read(T &x) {
ri f=1;x=0;register char ch=gc();
while(ch<'0'||ch>'9') {if (ch=='-') f=0;ch=gc();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
x=f?x:-x;
}
}
using IO::read;
namespace nanfeng{
#define FM(x) x>=MOD?x-MOD:x
#define cmax(x,y) ((x)>(y)?(x):(y))
#define cmin(x,y) ((x)>(y)?(y):(x))
#define FI FILE *IN
#define FO FILE *OUT
typedef long long ll;
static const int N=1e5+7,MOD=1e9+7;
int que[N],num[N],l[N],r[N],bit[N][21],cm[21],pce,n,opt;
ll tmp[21],nmc[21],ans1,ans2;
struct Trie{
#define ls(x) T[x].ch[0]
#define rs(x) T[x].ch[1]
struct trie{int ch[2],nm;}T[N*22];
int rt[N],tot;
inline void insert(int x,int pre,int &nw) {
nw=p(tot);ri cur=nw;
for (ri i(20);~i;--i) {
int p=(x>>i)&1;
T[cur].nm=T[pre].nm+1;
T[cur].ch[p^1]=T[pre].ch[p^1];
T[cur].ch[p]=p(tot);
cur=T[cur].ch[p],pre=T[pre].ch[p];
}
T[cur].nm=T[pre].nm+1;
}
inline int query(int sl,int pre,int cur) {
ri res=0,nm=0;
for (ri i(20);~i;--i) {
if (sl&cm[i]) {
if (nm+cm[i]>pce) {
int k=res;
res+=T[ls(cur)].nm-T[ls(pre)].nm;
cur=rs(cur),pre=rs(pre);
} else {
nm+=cm[i];
cur=ls(cur),pre=ls(pre);
}
} else {
if (nm+cm[i]>pce) {
int k=res;
res+=T[rs(cur)].nm-T[rs(pre)].nm;
cur=ls(cur),pre=ls(pre);
} else {
nm+=cm[i];
cur=rs(cur),pre=rs(pre);
}
}
}
return res;
}
}T;
inline void add(int x,int p) {
for (ri i(0);i<=20;p(i)) {
bit[p][i]=x&1;x>>=1;
if (!x) return;
}
}
inline int main() {
// FI=freopen("nanfeng.in","r",stdin);
// FO=freopen("nanfeng.out","w",stdout);
read(n),read(opt);
cm[0]=1;
for (ri i(1);i<=20;p(i)) cm[i]=cm[i-1]<<1;
for (ri i(1);i<=n;p(i)) read(num[i]);
ri tl=0;
for (ri i(1);i<=n;p(i)) {
add(num[i],i);
T.insert(num[i],T.rt[i-1],T.rt[i]);
while(tl&&num[que[tl]]<=num[i]) r[que[tl--]]=i-1;
l[i]=que[tl]+1;
que[p(tl)]=i;
for (ri j(0);j<=20;p(j)) bit[i][j]+=bit[i-1][j];
}
while(tl) r[que[tl--]]=n;
for (ri i(1);i<=n;p(i)) {
register ll res1=0,res2=0;
pce=num[i];
if (i-l[i]<=r[i]-i) {
for (ri j(0);j<=20;p(j)) nmc[j]=bit[r[i]][j]-bit[i-1][j];
ri len=r[i]-i+1;
for (ri j(l[i]);j<=i;p(j)) {
for (ri k(0);k<=20;p(k)) {
if (num[j]&(1<<k)) tmp[k]=len-nmc[k];
else tmp[k]=nmc[k];
res1+=tmp[k]*cm[k]%MOD;
res1=FM(res1);
}
res2+=T.query(num[j],T.rt[i-1],T.rt[r[i]])%MOD;
res2=FM(res2);
}
} else {
for (ri j(0);j<=20;p(j)) nmc[j]=bit[i][j]-bit[l[i]-1][j];
ri len=i-l[i]+1;
for (ri j(i);j<=r[i];p(j)) {
for (ri k(0);k<=20;p(k)) {
if (num[j]&(1<<k)) tmp[k]=len-nmc[k];
else tmp[k]=nmc[k];
res1+=tmp[k]*cm[k]%MOD;
res1=FM(res1);
}
res2+=T.query(num[j],T.rt[l[i]-1],T.rt[i])%MOD;
res2=FM(res2);
}
}
ans1+=res1*num[i]%MOD,ans1=FM(ans1);
ans2+=res2*num[i]%MOD,ans2=FM(ans2);
}
if (opt==1) printf("%lld
",ans1);
else if (opt==2) printf("%lld
",ans2);
else if (opt==3) printf("%lld
%lld
",ans1,ans2);
return 0;
}
}
int main() {return nanfeng::main();}