劇難(?
首先，先有個想法，對於相同顏色 (題目的魚口中含的那個東西)，假設有一個長度是a，另外一個是長度b，假設a>b，那，b是最大長度的集合，a是最大長度集合也一定可以完全包含，所以，對於那k種顏色，我們只要考慮長度最大的就好惹。
那，接下來，我們考慮以下算法：
(1)挑出最長的東西
(2)算出如果選了那個東西，可以造成多少集合
(3)之後再算的時候，把這個顏色固定挑0個！
上面那樣看起來是對的，但是.....
6
4
30000
6 4
9 1
8 2
13 3
2 1
18 4
對於上面那組測資，如果實現上面那樣的算法，總集合數量只會17，正確答案是20。
研究之後發現，漏考慮的三個集合分別是：
[1,2] (挑選第四隻和第五隻)
[1, 3, 4] (挑選1,4,5)
[3, 4] (挑選1,4)
為了方便說明，我定義一些函數：
POS(i,j) --> 第 i 種顏色的第 j 小的長度
BEST(i) --> 第 i 種顏色最長的長度
要怎麼把漏掉的case考慮進去呢(?)
可以發現，我們漏掉的case是：當有兩個顏色 x , y ，BEST(x) <= BEST(y) ，但是當 顏色 y 再用 BEST(y) 吃掉顏色 x 時，吃到的數量比用 BEST(x) 吃到的數量還要少 (假設 BEST(y)吃掉m個顏色x ， BEST(x)就可以吃到m + 1(自己) 個 )。 所以，要想盡辦法把上面那種case考慮進去~
#include <bits/stdc++.h> using namespace std; const int N = 500006; typedef pair<int,int> pii; #define F first #define S second #define SZ(x) ((int)(x).size()) int mod; int cnt[N]; struct Node { Node *lc,*rc; int val; Node():lc(NULL),rc(NULL),val(1){} void pull() { val = (lc->val*rc->val)%mod; } }; Node* Build(int L,int R) { Node* node = new Node(); if (L==R) { node->val = (cnt[L]+1)%mod; return node; } int mid=(L+R)>>1; node->lc = Build(L,mid); node->rc = Build(mid+1,R); node->pull(); return node; } Node* Build2(int L,int R) { Node* node = new Node(); if (L==R) return node; int mid=(L+R)>>1; node->lc = Build2(L,mid); node->rc = Build2(mid+1,R); return node; } void modify(Node* node,int L,int R,int pos,int del,bool set_1 = false) { if (L==R) { if (set_1) node->val = 1; else node->val = ((node->val+del)%mod + mod) % mod; return; } int mid=(L+R)>>1; if (pos <= mid) modify(node->lc,L,mid,pos,del,set_1); else modify(node->rc,mid+1,R,pos,del,set_1); node->pull(); return; } int query(Node* node,int L,int R,int l,int r) { if (l>R || L>r) return 1; else if (l<=L && R<=r) return node->val; int mid=(L+R)>>1; return (query(node->lc,L,mid,l,r) * query(node->rc,mid+1,R,l,r)) % mod; } pii p[N]; vector<int> G[N]; //store length bool vis[N]; int id[N]; //color position at segment tree int pos[N]; int clr[N]; int main () { int n,k; scanf("%d",&n); scanf("%d",&k); scanf("%d",&mod); for (int i=1;n>=i;i++) { scanf("%d %d",&p[i].F,&p[i].S); } sort(p+1,p+n+1); int ptr=0; for (int i=1;n>=i;i++) { G[ p[i].S ].push_back(p[i].F); if (p[i].F * 2 <= p[n].F) { cnt[ p[i].S ]++; ptr = i; } } Node* root1 = Build(1,k); Node* root2 = Build2(1,k); int ans=0; int nn=0; int dead_mn = 1000000007; for (int i=n;i>=1;i--) { if (vis[ p[i].S ]) continue; while (ptr > 0 && p[ptr].F*2 > p[i].F) { if (vis[ p[ptr].S ]) { modify(root2,1,k,id[p[ptr].S],-1); } else { modify(root1,1,k,p[ptr].S,-1); } --cnt[ p[ptr].S ]; //if (vis[ p[ptr].S ] && cnt[ p[ptr].S ] == 0) modify(root2,1,k,id[ p[ptr].S ],0,true); --ptr; } vis[ p[i].S ] = true; //cout << "i = " << i << endl; //cout << "ans += " << root1->val << endl; ans += root1->val; ans %= mod; modify(root1,1,k,p[i].S,0,true); //some searching if (nn != 0) { int now_cnt_clr = cnt[ p[i].S ]+1; //cout << "now_cnt_clr = " << now_cnt_clr << endl; int rr = 2* G[ p[i].S ][ now_cnt_clr-1 ] -1; //cout << "rr = " << rr << endl; if (rr >= pos[nn]) { int L=0,R=nn; //R is the answer while (R-L != 1) { int mid=(L+R)>>1; if (rr >= pos[mid]) R = mid; else L = mid; } //cout << "R = " << R << endl; //cout << "ans2 += " << query(root1,1,k,1,p[i].S-1) *1LL * query(root1,1,k,p[i].S+1,k) * query(root2,1,k,R,k) % mod << endl; ans += (query(root1,1,k,1,p[i].S-1) *1LL * query(root1,1,k,p[i].S+1,k) * (query(root2,1,k,R,k) -1LL+mod) % mod); ans %= mod; } } //final adding ++nn; clr[nn] = p[i].S; id[ p[i].S ] = nn; pos[nn] = p[i].F; modify(root2,1,k,id[ p[i].S ],cnt[ p[i].S ]); //cannot select 0 //modify(root1,1,k,p[i].S,0,true); if (cnt[ p[i].S ] == 0) modify(root2,1,k,id[ p[i].S ],0,true); dead_mn= min(dead_mn,G[ p[i].S ][0]); } printf("%d\n",ans); }
沒有留言:
張貼留言