「USACO 2020.12 Platinum」Cowmistry

Posted on Edited on In

「USACO 2020.12 Platinum」Cowmistry

看到样例解释突然就有了思路.jpg

令 \(m=\min\{2^t|2^t>k\}\) ，也就是 \(k\) 最高位+1

对于数轴，按照 \([im,(i+1)m)\) 分组，显然跨过分组的数之间异或 \(\ge m>k\) ，不合法，扔掉

对于每组，直接看做是 \([0,m-1]\) ，此时令 \(d=\frac{m}{2}\)

将 \([0,m-1]\) 分为 \([0,d-1],[d,m-1]\) ，显然两段之内的数相互异或的结果 \(<d\) ，一定合法

也就是说，长度为 \(d\) 的段内随意选3个都合法

下面考虑跨过 \(d\) 的贡献，显然是一边选一个，一边选两个，此时这些数之间的异或和 \(\ge d\)

以左边选一个为例，令 \(k'=k-d\)

\(O(k\log k)\)

考虑异或和中一定有 \(d\) 这一位，下面只需要对于 \(i\in[0,d-1]\) 暴力统计出 \([d,m]\) 中有多少个数 \(j\) 满足 \(i\oplus j\leq k'\)

可以前缀和之后 \(\log k\) 做到，从高到低依次考虑 \(k\) 每一个为1的二进制位 \(i\) ，如果查询的数这一位和 \(x\) 相同，那么下面可以任意选择

否则将 \(x\rightarrow x\oplus 2^i\)

实现如下

1
2
3
4
5
6
7
8
9
int Que(int x,int *A,int k){
	int ans=0;
	drep(i,19,0) if(k&(1<<i)) {
		int l=x&(~((1<<i)-1)),r=l+(1<<i)-1;
		ans+=A[r]-A[l-1];
		x^=1<<i;
	}
	return ans+A[x]-A[x-1];
}

得到个数 \(c\) 之后，接下来就是为 \(x\) 在 \(c\) 里选择两个匹配，就是 \(\sum \frac{c(c-1)}{2}\)

由此得到一个 \(O(k\log k)\) 做法，可以通过前三档数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
namespace part_klogk{
	const int N=1<<20|10;
	int m,A[N],B[N],ans;
	int Que(int x,int *A,int k){
		int ans=0;
		drep(i,19,0) if(k&(1<<i)) {
			int l=x&(~((1<<i)-1)),r=l+(1<<i)-1;
			ans+=A[r]-A[l-1];
			x^=1<<i;
		}
		return ans+A[x]-A[x-1];
	}
	void Solve(int l,int r) {
		int mid=(l+r)>>1;
		int c1=0,c2=0;
		rep(i,l,mid) c1+=A[i];
		rep(i,mid+1,r) c2+=A[i];
		ans=(ans+D3(c1))%P,ans=(ans+D3(c2))%P;
		rep(i,l,mid) if(A[i]) {
			int c=Que(i-l,B+mid+2,k-(m/2));
			ans=(ans+1ll*c*(c-1)/2)%P;
		}
		rep(i,mid+1,r) if(A[i]) {
			int c=Que(i-mid-1,B+l+1,k-(m/2));
			ans=(ans+1ll*c*(c-1)/2)%P;
		}
	}
	void Solve() {
		for(m=1;m<=k;) m<<=1;
		rep(i,1,n) rep(j,L[i],R[i]) A[j]++;
		rep(i,1,N-1) B[i]=B[i-1]+A[i-1];
		rep(i,0,R[n]/m) Solve(i*m,(i+1)*m-1);
		printf("%d\n",ans);
	}
}

\[\ \]

\(O(n\log k-n\log ^2 k)\)

考虑对于 \(k'\) ，问题降阶为求区间 \(a\) 中的每一个数 ， 在区间 \(b\) 中查询合法的个数 \(cnt_a\)

其中 \(a,b\) 区间可以认为对应相同的 \([0,L-1]\) ，但是出现元素不同

此时，继续采用上面的方法进行分组，分组对象变为两组区间

令 \(m'=\min\{2^t|2^t>k'\},d'=\frac{m}{2}\) ，分组之后

对于 \([0,d'-1],[d',m-1]\) ，显然两段之内异或 \(\leq d\) ，一定合法，加入答案 \(cnt_a\) 中

对于跨过区间的贡献，用下面的方法处理

左边区间对于右边区间继续递归进行查询，将得到的结果加上左边区间中数的个数

右边区间继续对于左边区间递归进行查询，将得到的结果加上右边区间中数的个数

问题不断降阶为子问题，会有 \(\log k\) 层子问题

每层子问题所有的区间可以分为 \(O(n)\) 段 特殊 的段

其他的部分要么完全覆盖要么为空，这些部分可以快速求出

发现答案如果用 \((num,cnt)\) 表示当前查询结果为 \(num\) 的个数为 \(cnt\)

每层可以用 \(O(n)\) 个不同的二元对表示结果

如此求得后，再自底向上合并得到答案

\[ \ \]

\[ \ \]

关于实现

如果真的按照上面的方法，一层层向下分裂区间，会面临着常数大，难以实现的问题

考虑将每个区间 \([L_i,R_i]\) 插入线段树 \([0,2^{30}-1]\)

显然得到 \(O(n\log k)\) 个节点，在底层完全覆盖的节点打上标记

先递归进行第一层的分裂区间操作，对于打上标记的节点可以分成 \(\frac{r-l+1}{m}\) 个完全覆盖区间

这些完全覆盖区间的答案可以 \(O(1)\) 求出

\[ \ \]

分裂完成后，每次查询的区间对用 \((a,b,L,k,f1,f2)\) 表示

其中 \(a\) 表示查询区间对应节点， \(b\) 表示被查询区间对应节点

\(L\) 表示区间长度， \(f1,f2\) 表示 \(a,b\) 是否继承到上层的完全覆盖标记

如此每次合并 \((ls_a,rs_b),(rs_a,ls_b)\) 的查询结果，加上另一边的贡献 即可

当 \(b\) 为空或者为完全覆盖时，答案可以 \(O(1)\) 得到

当 \(a\) 为空时，可以得到空答案

从这样的底层向上合并，每个元素被合并次数 \(O(\log k)\)

\[ \ \]

没有仔细分析复杂度，应该就是 \(O(n\log k-n\log ^2 k)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int,int> Pii;
#define mp make_pair
#define pb push_back
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
char IO;
int rd(){
    int s=0;
    while(!isdigit(IO=getchar()));
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return s;
}

const int N=2e4+10,P=1e9+7,I2=(P+1)/2,I3=(P+1)/3,U=1<<30;

int n,m,k;
int L[N],R[N];
int Check(){
    for(int i=k;i;i>>=1) if(~i&1) return 0;
    return 1;
}
int D3(int n){ return 1ll*n*(n-1)/2%P*(n-2)%P*I3%P; }
int D2(int n){ return 1ll*n*(n-1)/2%P; }

const int M=N*60;
int s[M],ls[M],rs[M],t[M],cnt,rt;
//在线段树上插入节点，打上标记，同时处理出size便于下面计算
void Ins(int &p,int l,int r,int ql,int qr){
    if(!p) p=++cnt;
    s[p]+=min(qr,r)-max(ql,l)+1;
    if(ql<=l && r<=qr) { t[p]=1; return; }
    int mid=(l+r)>>1;
    if(ql<=mid) Ins(ls[p],l,mid,ql,qr);
    if(qr>mid) Ins(rs[p],mid+1,r,ql,qr);
}

int ans;
// O(1)求出m
int Up(int k){ return 1<<(32-__builtin_clz(k)); }
typedef vector <Pii> V;
V Union(const V &A,const V &B){
    int p1=0,p2=0,s1=A.size(),s2=B.size();
    V R;
    // 这里是否归并并不影响复杂度
    while(p1<s1 || p2<s2) {
        if(p1<s1 && (p2==s2||A[p1]<B[p2])) {
            if(R.size() && R.back().first==A[p1].first) R.back().second+=A[p1].second;
            else R.pb(A[p1]);
            p1++;
        } else {
            if(R.size() && R.back().first==B[p2].first) R.back().second+=B[p2].second;
            else R.pb(B[p2]);
            p2++;
        }
    }
    return R;
}
V Calc(int a,int b,int L,int k,int f1,int f2){
    f1|=t[a],f2|=t[b];
    V Res;
    // 底层情况O(1)解决
    if(!f1 && !a) return Res;
    if(f2) return Res.pb(mp(k+1,f1?L:s[a])),Res;
    if(!b) return Res.pb(mp(0,f1?L:s[a])),Res;
    int m=Up(k);
    // L>m说明还要继续进行分裂
    if(L>m) return Union(Calc(ls[a],ls[b],L/2,k,f1,f2),Calc(rs[a],rs[b],L/2,k,f1,f2));
    // 进入降阶子问题，左查右，右查左
    k-=m/2;
    V A=Calc(ls[a],rs[b],L/2,k,f1,f2);
    for(auto &i:A) i.first+=f2?L/2:s[ls[b]];
    V B=Calc(rs[a],ls[b],L/2,k,f1,f2);
    for(auto &i:B) i.first+=f2?L/2:s[rs[b]];
    return Union(A,B);
}

int cm;
// 第一次分裂
void Solve(int p,int L){
    if(!p) return;
    // 完全覆盖的部分答案可以快速求出
    if(t[p]) { cm+=L/m; return; }
    // 已经完成分裂，此时进入第一层子问题
    if(L==m) {
        // 贡献分为 
        // 左选3 ， 右选 3
        ans=(ans+D3(s[ls[p]]))%P,ans=(ans+D3(s[rs[p]]))%P;
        // 左1，右2
        V A=Calc(ls[p],rs[p],m/2,k-m/2,0,0);
        // 左2，右1
        V B=Calc(rs[p],ls[p],m/2,k-m/2,0,0);
        for(auto i:A) ans=(ans+1ll*D2(i.first)*i.second)%P;
        for(auto i:B) ans=(ans+1ll*D2(i.first)*i.second)%P;
        return;
    }
    Solve(ls[p],L/2),Solve(rs[p],L/2);
}
int main(){
    n=rd(),k=rd();
    rep(i,1,n) { int l=rd(),r=rd(); Ins(rt,0,U-1,l,r); }
    m=Up(k),Solve(rt,U);
    // O(1)求得完全覆盖部分的答案
    int t=(2ll*D3(m/2)+1ll*D2(k-m/2+1)*m)%P;
    ans=(ans+1ll*cm*t)%P;
    printf("%d\n",ans);
}