比较文本

查找两个文本文件之间的差异

Real-time diff

Unified diff

Collapse lines

Highlight change

Syntax highlighting

工具

「USACO 2020.12 Platinum」Cowmistry

Created 27 days agoDiff never expires

The two files are identical

There is no difference to show between these two files

0 removals

113 lines

0 additions

113 lines

#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);

}

已保存差异

原始文本

Open file

#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);
}

更改后文本

Open file

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; }