逛公园
琥珀色黄昏像糖在很美的远方,思念跟影子在傍晚一起被拉长……
题目描述
小 B 带着 BF 去逛公园,公园一共有 n 个景点,标号为 1 . . . n。景点之间有 m 条路径相连。
小 B 想选择编号在一段区间 [l, r] 内的景点来游玩,但是如果这些景点的诱导子图形成了环,那么 BF 将会不高兴。
小 B 给出很多个询问 [x, y],想让你求有多少个区间 [l, r] 满足 x ≤ l, r ≤ y 且不会使 BF不高兴。
思路
首先我们可以找出所有的环。一个环对答案的影响只取决于其上点编号的最值。O(n) 预处理出所有的环左右端点的编号,将问题转化为有不包含一些区间的合法区间数量后,我们令 $faraway_i$ 为以 $i$ 为左端点的合法区间的右端点最大值,发现 $faraway$ 数组是单调的。于是对于每个询问 $[l,r]$,在 $[l,r]$ 中二分找出最大的 $p$ 使得 $faraway_p < r$,然后将询问拆成两部分分别计算贡献。
- 如何求 $faraway$ 数组:左端点排序维护对当前点有影响的环,优先队列维护这些环右端点的值。
- 如何统计答案:前缀和 + 等差数列求和。
代码
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 |
#include <bits/stdc++.h> #define maxn 501010 #define ll long long #define chkmin(a,b) (a>b?a=b:NULL) #define chkmax(a,b) (a<b?a=b:NULL) using namespace std; struct Edge{ int to,next; Edge(int a=0,int b=0){ to=a,next=b; } }l[maxn<<1]; struct Ring{ int l,r,id; Ring(int a=INT_MAX,int b=0,int c=0){ l=a,r=b,id=c; } bool operator < (const Ring &x) const{ return r>x.r; } }r[maxn]; struct ios{ inline char read(){ static const int IN_LEN=1<<18|1; static char buf[IN_LEN],*s,*t; return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++; } template <typename _Tp> inline ios & operator >> (_Tp&x){ static char c11,boo; for(c11=read(),boo=0;!isdigit(c11);c11=read()){ if(c11==-1)return *this; boo|=c11=='-'; } for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0'); boo&&(x=-x); return *this; } }io; bool cmpring(Ring x,Ring y){ return x.l<y.l; } int head[maxn],sea[maxn],cnt,tot,n,m,q; int bel[maxn],vis[maxn],fa[maxn]; int faraway[maxn]; ll subans[maxn]; inline void add(int a,int b){ l[++cnt]=Edge(b,head[a]); head[a]=cnt; } inline void color(int u,int v){ ++tot; int pos=u; chkmin(r[tot].l,v); chkmax(r[tot].r,v); while(pos!=v){ chkmin(r[tot].l,pos); chkmax(r[tot].r,pos); pos=fa[pos]; } } inline void search(int u,int f){ vis[u]=1; for (int i=head[u];i;i=l[i].next){ int v=l[i].to; if (v==f) continue; if (!vis[v]){ fa[v]=u; search(v,u); } else if (vis[v]==1) color(u,v); } vis[u]=2; } priority_queue<Ring>t; int del[maxn]; int main(){ freopen("graph.in","r",stdin); freopen("graph.out","w",stdout); io>>n>>m; for (register int i=1,t2,t1;i<=m;++i){ io>>t1>>t2; add(t1,t2),add(t2,t1); } for (register int i=1;i<=n;++i) if (!vis[i]) search(i,0); sort(r+1,r+1+tot,cmpring); for (register int i=1;i<=tot;++i) r[i].id=i,t.push(r[i]); int pos=1,cur=1; for (register int i=1;i<=n;++i){ while(cur<=tot&&r[cur].l<i) del[cur]=1,cur++; while(!t.empty()&&del[t.top().id]) t.pop(); if (!t.empty()) pos=t.top().r-1; else pos=n; faraway[i]=pos; subans[i]=pos-i+1; } for (register int i=1;i<=n;++i) subans[i]+=subans[i-1]; io>>q; for (register int i=1,l,r;i<=q;++i){ io>>l>>r; ll res=0; int k=lower_bound(faraway+1,faraway+1+n,r)-faraway-1; k=max(k,l-1); res+=subans[k]-subans[l-1]; res+=1ll*(r-k+1)*(r-k)/2; printf("%lld\n",res); } } |
风筝
当一阵风吹来,风筝飞上天空,为了你,而祈祷,而祝福,而感动……
题目描述
oyiya 在 AK 了 IOI 之后来到了乡下,在田野中玩耍,放松身心。
他发现前面有一排小朋友在放风筝,每一个风筝有一个高度 hi,风筝的高度可能会随着小朋友的心情而改变。这时,毒瘤的 oyiya 有了一个毒瘤的 idea,他想知道改变高度之后风筝的最长严格上升子序列。oyiya 太强了表示并不想做这种水题,你能解决这个问题吗?
思路
我们先求出新序列经过这个点的 LIS 长度,然后将它与原序列 LIS 长度(考虑是否减一)取最大值。原序列 LIS 长度需要减一当且仅当这个位置是原序列 LIS 的必经之处。
解决以上问题只需要预处理出两个数组:$pre_i$ 和 $suf_i$,分别表示不考虑修改,以第 $i$ 个点为结尾 / 开头的 LIS 长度。对于第 $i$ 个点,如果满足 $pre_i+suf_i=len+1$(len 为 总LIS 长度),则这个点在 LIS 的第 $pre_i$ 位上。枚举所有的位置,如果只有 $i$ 在这一位上,则 $i$ 是 LIS 的必经之处。
现在我们考虑修改位置 $p$ 上的值为 $h$。如果新序列 LIS 不经过 $p$,答案就是 $len$ 或者 $len-1$,取决于这个点是不是原序列 LIS 必经之处。如果新序列 LIS 经过 $p$,我们找出 $p$ 之前 / 之后第一个小于 / 大于 $h$ 的位置,经过 $p$ 和这两个位置的子序列才可能是新序列 LIS。
如何计算后一种情况呢?将问题离线,可以在计算 $pre, suf$ 数组的同时更新后一种情况的答案。
代码
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 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #define maxn 500005 using namespace std; int n,m,len,a[maxn],pre[maxn]; int suf[maxn],f[maxn],rank[maxn]; struct Node{ int a,b,id,ans; }q[maxn]; bool afirst(Node x,Node y) {return x.a<y.a;} bool idfirst(Node x,Node y) {return x.id<y.id;} int main(){ freopen("kite.in","r",stdin); freopen("kite.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=m;i++){ scanf("%d%d",&q[i].a,&q[i].b); q[i].id=i; } sort(q+1,q+m+1,afirst); memset(f,0x3f,sizeof(f)); for(int i=1,j=1;i<=n;i++){ while(j<=m && q[j].a<=i){ int pos=lower_bound(f+1,f+n+1,q[j].b)-f; q[j].ans+=pos;j++; } int pos=lower_bound(f+1,f+n+1,a[i])-f; pre[i]=pos;f[pos]=a[i]; len=max(len,pre[i]); } memset(f,0x3f,sizeof(f)); for(int i=n,j=m;i;i--){ while(j>=1&&q[j].a>=i){ int pos=lower_bound(f+1,f+n+1,-q[j].b)-f; q[j].ans+=pos;j--; } int pos=lower_bound(f+1,f+n+1,-a[i])-f; suf[i]=pos;f[pos]=-a[i]; } for(int i=1;i<=n;i++) if(suf[i]+pre[i]==len+1) rank[pre[i]]++; for(int i=1;i<=m;i++){ if(suf[q[i].a]+pre[q[i].a]==len+1) q[i].ans=max(q[i].ans-1,len-(rank[pre[q[i].a]]==1)); else q[i].ans=max(q[i].ans-1,len); } sort(q+1,q+m+1,idfirst); for(int i=1;i<=m;i++) printf("%d\n",q[i].ans); } |
种花
院子落叶,跟我的思念厚厚一叠;窗台蝴蝶,像诗里纷飞的美丽章节……
题目描述
小 H 是一个喜欢养花的女孩子。
她买了 n 株花,编号为一里香,二里香……七里香……n 里香,她想把这些花分别种在 n 个不同的花盆里。
对于一种方案,第 $i$ 个花盆里种的是 $a_i$ 里香,小 H 定义其美丽值为:
$$\sum\limits_{i<j,a_i>a_j}(j-i)*(a_i-a_j)$$
另外,由于一些特殊原因,第 $i$ 个花盆里不能种 $p_i$ 里香。
现在,小 H 想知道,所有合法方案的美丽值的和是多少。你能帮她解决这个问题吗?
思路
首先我们发现这是一个错排问题。
$f_{i,j}$ 表示一共有 $(i + j)$ 个元素,其中 $j$ 个没有限制,另外 $i$ 个被禁止放入一个位置。
我们先计算 $j=0$ 的情况,也就是经典的错排问题,此时每个元素都有限制。
首先,考虑加入第 $x$ 个元素,把它放在位置 $k$,一共有 $x-1$ 种方案;
对于原来在位置 $k$ 的元素,有两种情况:
- 把它放到位置 $x$,剩下 $x-2$ 个元素错排即可,有 $f_{x-2,0}$ 种方案;
- 第 $k$ 个元素不放到位置 $x$,这时对于这 $x-1$ 个元素的错排,有 $f_{x-1,0}$ 种方案。
现在我们加入一个没有限制的元素。如果该元素放置的位置是有限制的,那么以前有限制的元素就变成了没有限制的了,有 $x$ 种选择方法,剩下的元素的放置方案数为 $f_{x−1,y}$;如果该元素放置的位置是没有限制的,那么有 $y$ 种选择方法,剩下的元素的放置方案数为 $f_{x,y−1}$。
于是得到转移方程:
$$f_{0,0} = 1$$
$$f_{x,0} = (x − 1)(f_{x−1,0} + f_{x−2,0})$$
$$f_{x,y} = f_{x,y−1} × y + x × f_{x−1,y}$$
回到这道题目本身。我们枚举每一对 $i,j (i<j)$,确定 $(j-i)$ 的值之后,剩下的贡献需要分三种情况讨论:
- $p_j$ 放在 $i$ 上,$p_i$ 放在 $j$ 上,那么有 $f_{n-2,0}$ 种方案,贡献 $a_1 = \max (0,p_j-p_i)$。
- 上述两个条件只有一个成立,那么有 $f_{n-3,1}$ 种方案,贡献 $a_2=\sum_{k=1}^{p_j-1}k+\sum_{k=1}^{n-p_i}k-2a_1$。
- 上述条件均不成立,那么有 $f_{n-4,2}$ 种方案,贡献 $a_3=\sum_{k=2}^n (n-k+1)k-a_1-a_2-\sum_{k=1}^{p_i-1}k-\sum_{k=1}^{n-p_j}k+\max (0,p_i-p_j)$。
我们是如何计算 $a_2$ 的呢?显然,当 $p_j$ 放在 $i$ 上,对于所有满足条件的 $a_j$,有$a_j-a_i = a_j-p_j$,它们的和为 $\sum_{k=1}^{p_j-1}k$。类似地,我们求出 $p_i$ 放在 $j$ 上的答案为 $\sum_{k=1}^{n-p_i}k$。由于两次计算导致和 $a_1$ 重复,故减去 $2a_1$。
对于 $a_3$,我们枚举所有的 $a_i < a_j$,它们差值的和为 $\sum_{k=1}^{n-p_i}k$。这个值包含了 $a_1, a_2$,以及非法方案 $(a_i=p_i, a_j=p_j)$,故全部减去,两种非法的方案有重复的部分,故加上 $\max (0,p_i-p_j)$。
至此,我们可以直接计算答案了:
$$\sum_{i<j}(j-i)(a_1 f_{n-2,0}+a_2 f_{n-3,1}+a_3 f_{n-4,2})$$
代码
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 |
#include <bits/stdc++.h> #define maxn 5010 #define ll long long #define md 1000000009 using namespace std; inline void inc(int &x,int y){x=x+y>=md?x+y-md:x+y;} inline void dec(int &x,int y){x=x-y<0?x-y+md:x-y;} int f[3][maxn],p[maxn],n; int s[maxn],sum,ans,t1,t2,t3; void init(){ f[0][0]=1; for (register int i=2;i<=n;++i) f[0][i]=1ll*(i-1)*(f[0][i-1]+f[0][i-2])%md; for (register int i=0;i<=n;++i) for (register int j=1;j<=2;++j) inc(f[j][i],1ll*f[j-1][i]*j%md), inc(f[j][i],(1ll*f[j][max(i-1,0)]*i%md)); } int main(){ scanf("%d",&n); init(); if (n>=2) t1=f[0][n-2]; if (n>=3) t2=f[1][n-3]; if (n>=4) t3=f[2][n-4]; for (register int i=1;i<=n;++i) scanf("%d",p+i); for (register int i=1;i<=n;++i) s[i]=s[i-1]+i; for (register int i=1;i<=n;++i) inc(sum,s[i-1]); for (register int i=1;i<=n;++i){ for (register int j=i+1;j<=n;++j){ int res=0; int a1=max(0,p[j]-p[i]); int a2=(s[p[j]-1]+s[n-p[i]])%md; dec(a2,2*a1%md); int a3=sum;dec(a3,a1),dec(a3,a2); dec(a3,s[p[i]-1]),dec(a3,s[n-p[j]]); inc(a3,max(0,p[i]-p[j])); inc(res,1ll*a1*t1%md); inc(res,1ll*a2*t2%md); inc(res,1ll*a3*t3%md); inc(ans,1ll*(j-i)*res%md); } } printf("%d",ans); } |