### 逛公园

#### 思路

• 如何求 $faraway$ 数组：左端点排序维护对当前点有影响的环，优先队列维护这些环右端点的值。
• 如何统计答案：前缀和 + 等差数列求和。

#### 代码

#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{
static const int IN_LEN=1<<18|1;
static char buf[IN_LEN],*s,*t;
}
template <typename _Tp> inline ios & operator >> (_Tp&x){
static char c11,boo;
if(c11==-1)return *this;
boo|=c11=='-';
}
boo&&(x=-x);
return *this;
}
}io;
bool cmpring(Ring x,Ring y){
return x.l<y.l;
}
int bel[maxn],vis[maxn],fa[maxn];
int faraway[maxn];
ll subans[maxn];
}
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;
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;
}
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 之后来到了乡下，在田野中玩耍，放松身心。

#### 代码

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


### 种花

#### 题目描述

$$\sum\limits_{i<j,a_i>a_j}(j-i)*(a_i-a_j)$$

#### 思路

$f_{i,j}$ 表示一共有 $(i + j)$ 个元素，其中 $j$ 个没有限制，另外 $i$ 个被禁止放入一个位置。

1. 把它放到位置 $x$，剩下 $x-2$ 个元素错排即可，有 $f_{x-2,0}$ 种方案；
2. 第 $k$ 个元素不放到位置 $x$，这时对于这 $x-1$ 个元素的错排，有 $f_{x-1,0}$ 种方案。

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

• $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)$。

$$\sum_{i<j}(j-i)(a_1 f_{n-2,0}+a_2 f_{n-3,1}+a_3 f_{n-4,2})$$

#### 代码

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