USACO 2020 February Contest, Platinum Problem 3. Help Yourself

USACO 2020 February Contest, Platinum Problem 3. Help Yourself

Bessie has been given NN (1N1051≤N≤105) segments on a 1D number line. The iith segment contains all reals xx such that lixrili≤x≤ri.

Define the union of a set of segments to be the set of all xx that are contained within at least one segment. Define the complexity of a set of segments to be the number of connected regions represented in its union, raised to the power of KK (2K102≤K≤10).

Bessie wants to compute the sum of the complexities over all 2N2N subsets of the given set of NN segments, modulo 109+7109+7.

Normally, your job is to help Bessie. But this time, you are Bessie, and there is no one to help you. Help yourself!

 

SCORING

  • Test case 2 satisfies N16N≤16.
  • Test cases 3-5 satisfy N1000N≤1000K=2K=2.
  • Test cases 6-8 satisfy N1000N≤1000.
  • For each T[9,16],T∈[9,16], test case TT satisfies K=3+(T9)K=3+(T−9).

 

INPUT FORMAT (file help.in):

The first line contains NN and KK.Each of the next NN lines contains two integers lili and riri. It is guaranteed that li<rili<ri and all li,rili,ri are distinct integers in the range 12N.1…2N.

 

OUTPUT FORMAT (file help.out):

Output the answer, modulo 109+7109+7.

 

SAMPLE INPUT:

3 2
1 6
2 3
4 5

SAMPLE OUTPUT:

10

The complexity of each nonempty subset is written below.

 

{[1,6]}1,{[2,3]}1,{[4,5]}1{[1,6]}⟹1,{[2,3]}⟹1,{[4,5]}⟹1

 

{[1,6],[2,3]}1,{[1,6],[4,5]}1,{[2,3],[4,5]}4{[1,6],[2,3]}⟹1,{[1,6],[4,5]}⟹1,{[2,3],[4,5]}⟹4

 

{[1,6],[2,3],[4,5]}1{[1,6],[2,3],[4,5]}⟹1

The answer is 1+1+1+1+1+4+1=101+1+1+1+1+4+1=10.

 

Problem credits: Benjamin Qi

USACO 2020 February Contest, Platinum Problem 3. Help Yourself 题解(翰林国际教育提供,仅供参考)

题解请注册登录查看

[/hide]

(Analysis by Benjamin Qi)

Sort the segments by left coordinate, and try placing the segments into a subset in this order. The only information we need to store about the collection of segments that are members of the subset is the rightmost coordinate in this collection.

For each 0i2N0≤i≤2Ndp[i]dp[i] will store information about collections with rightmost coordinate ii. Suppose that collection cc contains exactly acac segments in this union. Then for each 0jK0≤j≤K we'll store

dp[i][j]=cajc.dp[i][j]=∑cacj.

So dp[i][0]dp[i][0] stores the number of collections with rightmost coordinate iidp[i][1]dp[i][1] stores the sum of the number of segments in the union of each collection with rightmost coordinate ii, and so on.

If we add a segment [l,r][l,r] to a collection cc with rightmost coordinate ii,

 

  1. If i<li<l then acac increases by one and the rightmost coordinate becomes rr.
  2. Otherwise if i<ri<r then acac remains unchanged and the rightmost coordinate becomes rr.
  3. Otherwise acac and the rightmost coordinate remain unchanged.

To account for case 1, we need to find the updated value of dp[i]dp[i] after adding one to each acac. Call the result adv(dp[i]).adv(dp[i]). By the binomial theorem,

adv(dp[i])[j]=c(ac+1)j=k=0j(jk)akc=k=0j(jk)dp[i][k].adv(dp[i])[j]=∑c(ac+1)j=∑k=0j(jk)ack=∑k=0j(jk)dp[i][k].

This update can be performed in O(K2)O(K2) time, giving a DP solution that runs in O(N2K2)O(N2K2) or O(N2+NK2)O(N2+NK2) time.

To receive full credit, use a lazy segment tree that supports point updates, range sum queries, and range multiplication updates.

 

  1. For case 1, add adv(l1i=0dp[i])adv(∑i=0l−1dp[i]) to dp[r]dp[r].
  2. For case 2, add r1i=ldp[i]∑i=lr−1dp[i] to dp[r]dp[r].
  3. For case 3, multiply dp[i]dp[i] by two for each i>ri>r.

After the above operations are performed for each segment, the final answer will be 2Ni=0dp[i][K]∑i=02Ndp[i][K]. This can be done in O(NK2+NKlogN)O(NK2+NKlog⁡N) time; the first term is for calculating adv()adv() and the second is for the range updates and queries. (In fact, it's possible to remove the NK2NK2 term, but I won't describe the method here.)

 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define f first
#define s second

const int MOD = 1e9+7; 

void setIO(string s) {
  ios_base::sync_with_stdio(0); cin.tie(0); 
  freopen((s+".in").c_str(),"r",stdin);
  freopen((s+".out").c_str(),"w",stdout);
}
 
struct mi {
  int v; explicit operator int() const { return v; }
  mi(ll _v) : v(_v%MOD) { v += (v<0)*MOD; }
  mi() : mi(0) {}
};
mi operator+(mi a, mi b) { return mi(a.v+b.v); }
mi operator-(mi a, mi b) { return mi(a.v-b.v); }
mi operator*(mi a, mi b) { return mi((ll)a.v*b.v); }
 
vector<pair<int,int>> v;
mi res;
int N,K;

typedef array<mi,11> T;
mi cum[11][11];
 
T adv(T p) {
  for (int i = K; i >= 0; --i) for (int j = i; j <= K; ++j)
    cum[i][j] = (i == j ? p[i] : cum[i][j-1]+cum[i+1][j]);
  T res; for (int i = 0; i <= K; ++i) res[i] = cum[0][i];
  return res;
}
 
T seg[1<<18];
mi lazy[1<<18];
 
vector<int> y = {0};
 
void push(int ind, int L, int R) {
  if (lazy[ind].v == 1) return;
  for (int i = 0; i <= K; ++i) seg[ind][i] = seg[ind][i]*lazy[ind];
  if (L != R) {
    lazy[2*ind] = lazy[2*ind]*lazy[ind];
    lazy[2*ind+1] = lazy[2*ind+1]*lazy[ind];
  }
  lazy[ind] = 1;
}
 
void mul(int pos, int ind, int L, int R) {
  push(ind,L,R);
  if (pos > R) return;
  if (pos <= L) {
    lazy[ind] = 2;
    push(ind,L,R);
    return;
  }
  int M = (L+R)/2;
  mul(pos,2*ind,L,M); mul(pos,2*ind+1,M+1,R);
  for (int i = 0; i <= K; ++i) seg[ind][i] = seg[2*ind][i]+seg[2*ind+1][i];
}
 
void upd(int pos, const T& val, int ind, int L, int R) {
  push(ind,L,R);
  if (pos < L || pos > R) return;
  for (int i = 0; i <= K; ++i) seg[ind][i] = seg[ind][i]+val[i];
  if (L == R) return;
  int M = (L+R)/2;
  if (pos <= M) upd(pos,val,2*ind,L,M);
  else upd(pos,val,2*ind+1,M+1,R);
}
 
void query(int lo, int hi, T& t, int ind, int L, int R) {
  push(ind,L,R);
  if (hi < L || lo > R) return;
  if (lo <= L && R <= hi) { 
    for (int i = 0; i <= K; ++i) t[i] = t[i]+seg[ind][i]; 
    return; 
  }
  int M = (L+R)/2;
  query(lo,hi,t,2*ind,L,M); query(lo,hi,t,2*ind+1,M+1,R);
}
 
void ad(int a, int b) {
  auto i1 = lower_bound(begin(y),end(y),a)-begin(y)-1;
  auto i2 = lower_bound(begin(y),end(y),b)-begin(y);
  T A = T(); query(0,i1,A,1,0,N); A = adv(A);
  T B = T(); query(i1+1,i2,B,1,0,N); 
  for (int i = 0; i <= K; ++i) A[i] = A[i]+B[i];
  upd(i2,A,1,0,N);
  mul(i2+1,1,0,N);
}
 
int main() {
  setIO("help");
  for (int i = 1; i < (1<<18); ++i) lazy[i] = 1;
  cin >> N >> K; v.resize(N); 
  for (auto& t: v) {
    cin >> t.f >> t.s;
    y.push_back(t.s);
  }
  sort(begin(v),end(v)); sort(begin(y),end(y));
  T ori = T(); ori[0] = 1;
  upd(0,ori,1,0,N);
  for (auto t: v) ad(t.f,t.s);
  T res = T(); query(0,N,res,1,0,N);
  cout << res[K].v << "\n";
}

[/hide]

翰林国际教育资讯二维码