2020.05.20【省選B組】模拟

今天的題都比較巧妙。

T1：首先我們設sum[i]表示前i個位置有多少個精靈，設p[i]=sum[i]-i。接着我們不難發現對于最小的一個p[m]，一定不會存在有精靈從m走到m+1。

證明：如果存在精靈從m走到m+1，那麼一定存在一個位置x使得從x到m的精靈數大于從x到m的位置數，即sum[m]-sum[x-1]>m-(x-1)，移項得sum[m]-m>sum[x-1]-(x-1)，即p[m]>p[x-1]。這與p[m]最小沖突，是以假設不成立，結論成立。

有了這一條性質之後我們就可以找一個p[m]最小的m，然後在m和m+1開始斷開，化環為鍊，接着順着掃一遍貪心就好了。貪心的過程就是每次盡量找一個最小的但大于目前位置的精靈，找不到就找一個最小的精靈，這個可以用線段樹維護。時間複雜度O(nlogn)。

T2：首先我們發現一個最終的答案肯定是在原序列中以某個位置為開頭，找一個以目前位置為起點的最長上升子序列和一個最長下降子序列，這兩個子序列合起來就是答案。這個手推一下就明白了。

是以現在我們用樹狀數組求出以每一個位置為起點的最長上升子序列和最長下降子序列的長度和方案數，設為fa、fb、ga、gb。然後最終最長的長度就是max(fa[i]+fb[i]-1)，方案數就是sum(ga[i]*gb[i]*2^(n-maxlen))（fa[i]+fb[i]-1==maxlen）。之是以要乘一個2^(n-maxlen)是因為剩下的數可以随便放。

樹狀數組求最長上升子序列及方案數：

首先要求最長長度。這個還是比較簡單的，因為是上升是以我們每一次查詢的是1~a[i]-1的最大值，這個是可以用樹狀數組維護的。如果是求最長下降子序列的話把a反過來就行了。

接着要求方案數。在維護樹狀數組時設f[i][1]表示目前區間的最大值，f[i][2]表示目前區間最大值的方案數。在查詢時，要把所有達到最大值的區間的f[i][2]加上。修改時要把目前的g加入f[i][2]中。這樣就可以了。

貼一下代碼：

ll find1(ll v)
{
	ll i=v,m=0;
	while(i>=1)
	{
		if(f[i][1]>m)m=f[i][1];
		i=i-(i&(-i));
	}
	return m;
}
ll find2(ll v,ll m)
{
	ll i=v,s=0;
	while(i>=1)
	{
		if(f[i][1]==m)s=(s+f[i][2])%mod;
		i=i-(i&(-i));
	}
	return s;
}
ll change(ll v,ll m,ll s)
{
	ll i=v;
	while(i<=ma)
	{
		if(m>f[i][1]){f[i][1]=m;f[i][2]=s;}
		else if(m==f[i][1])f[i][2]=(f[i][2]+s)%mod;
		i=i+(i&(-i));
	}
}           

T3：題解待更新。