T1 JZOI5246 Trip
Problem
有一串长为 \(n\) 的序列 \(a\)，有 \(m\) 组询问，每组询问给出一个区间，求区间内有多少个数满足以下条件之一：
- 在区间内，它的左侧不存在大于它的数。
- 在区间内，它的右侧不存在大于它的数。
Solution
离散化，用权值线段树求出序列上每个数左边和右边第一个比它大的数的位置，记为 \(L,R\)。
因此对于每组询问 \([l,r]\)，我们要求 \([l,r]\) 中所有 \(L<l\) 或 \(r<R\) 的点，可以大减小来求：我们先求出序列中所有 \(L<l\) 或 \(r<R\) 的点，减去这之中不在 \([l,r]\) 中的点。而我们发现不在区间中的点一定都是满足 \(L<l\) 或 \(r<R\) 的，因此直接减去 \(n-(r-l+1)\) 。
现在问题转化为一个二维数点：\(n\) 个点 \((L,R)\)，\(m\) 组询问 \(l,r\)，求 \(L<l\) 或 \(r<R\) 的点，树状数组做即可。代码中是先求的 1 号部分，然后统一求的 2 3 号部分，避免为了 3 号部分又重新倒着做一遍。
代码
#include<bits/stdc++.h>
#define lch (pos<<1)
#define rch (pos<<1|1)
#define getmid int mid=(l+r)/2
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar __getchar
inline char __getchar(){
static char ch[1<<20],*l,*r;
return (l==r&&(r=(l=ch)+fread(ch,1,1<<20,stdin),l==r))?EOF:*l++;
}
#endif
template<class T>inline void rd(T &x){
T res=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while('0'<=ch && ch<='9'){res=res*10+ch-'0';ch=getchar();}
x=res*f;
}
template<class T>inline void wt(T x,char endch='\0'){
static char wtbuff[20];
static int wtptr;
if(x==0){
putchar('0');
}
else{
if(x<0){x=-x;putchar('-');}
wtptr=0;
while(x){wtbuff[wtptr++]=x%10+'0';x/=10;}
while(wtptr--) putchar(wtbuff[wtptr]);
}
if(endch!='\0') putchar(endch);
}
typedef pair<int,int> pii;
const int MAXN=1e6+5;
int n,m,a[MAXN],na[MAXN],buck[MAXN],len,ans[MAXN];
pii rg[MAXN];
struct NQRY{
int first,second,id;
bool operator < (const NQRY y){
return first<y.first;
}
}qry[MAXN];
class SegTreeMax{
private:
int t[MAXN<<2];
inline void pushup(int pos){
t[pos]=max(t[lch],t[rch]);
}
public:
void update(int pos,int l,int r,int aim,int val){
if(l==r){
t[pos]=val;
return;
}
getmid;
if(aim<=mid) update(lch,l,mid,aim,val);
else update(rch,mid+1,r,aim,val);
pushup(pos);
}
int query(int pos,int l,int r,int ll,int rr){
if(ll>rr) return 0;
if(ll<=l && r<=rr){
return t[pos];
}
getmid,res=0;
if(ll<=mid) res=max(res,query(lch,l,mid,ll,rr));
if(mid<rr) res=max(res,query(rch,mid+1,r,ll,rr));
return res;
}
}stmax;
class SegTreeMin{
private:
int t[MAXN<<2];
inline void pushup(int pos){
t[pos]=min(t[lch],t[rch]);
}
public:
SegTreeMin(){
memset(t,0x3f,sizeof(t));
}
void update(int pos,int l,int r,int aim,int val){
if(l==r){
t[pos]=val;
return;
}
getmid;
if(aim<=mid) update(lch,l,mid,aim,val);
else update(rch,mid+1,r,aim,val);
pushup(pos);
}
int query(int pos,int l,int r,int ll,int rr){
if(ll>rr) return 0x3f3f3f3f;
if(ll<=l && r<=rr){
return t[pos];
}
getmid,res=0x3f3f3f3f;
if(ll<=mid) res=min(res,query(lch,l,mid,ll,rr));
if(mid<rr) res=min(res,query(rch,mid+1,r,ll,rr));
return res;
}
}stmin;
class Fenwick{
private:
int t[MAXN];
inline int lowbit(int x){
return x&(-x);
}
public:
inline void reset(){
memset(t,0,sizeof(t));
}
inline void add(int pos,int v){
while(pos<=n){
t[pos]+=v;
pos+=lowbit(pos);
}
}
inline int ask(int pos){
int res=0;
while(pos>0){
res+=t[pos];
pos-=lowbit(pos);
}
return res;
}
inline int ask_range(int l,int r){
if(l>r) return 0;
if(l<=1) return ask(r);
else return ask(r)-ask(l-1);
}
}fw;
int main(){
rd(n);rd(m);
for(int i=1;i<=n;i++){
rd(a[i]);
buck[i]=a[i];
}
for(int i=1;i<=m;i++){
rd(qry[i].first);rd(qry[i].second);
qry[i].id=i;
}
sort(buck+1,buck+1+n);
len=unique(buck+1,buck+1+n)-buck-1;
for(int i=1;i<=n;i++)
na[i]=lower_bound(buck+1,buck+1+len,a[i])-buck;
for(int i=1,res;i<=n;i++){
res=stmax.query(1,1,len,na[i]+1,len);
if(res==0) rg[i].first=1;
else rg[i].first=res+1;
stmax.update(1,1,len,na[i],i);
}
for(int i=n,res;i>=1;i--){
res=stmin.query(1,1,len,na[i]+1,len);
if(res==0x3f3f3f3f) rg[i].second=n;
else rg[i].second=res-1;
stmin.update(1,1,len,na[i],i);
}
sort(qry+1,qry+1+m);
sort(rg+1,rg+1+n);
for(int i=1,ptrqry=0,ptrrg=0;i<=n;i++){
while(ptrrg<n && rg[ptrrg+1].first<=i){
ptrrg++;
fw.add(rg[ptrrg].second,1);
}
while(ptrqry<m && qry[ptrqry+1].first<=i){
ptrqry++;
ans[qry[ptrqry].id]+=fw.ask(qry[ptrqry].second-1);
}
if(ptrrg>=n && ptrqry>=m) break;
}
for(int i=1;i<=m;i++){
ans[qry[i].id]+=fw.ask_range(qry[i].second,n);
ans[qry[i].id]-=(qry[i].first-1)+(n-qry[i].second);
}
for(int i=1;i<=m;i++){
wt(ans[i],'\n');
}
return 0;
}
T2 QOJ1173 Knowledge Is...
Problem
有 \(n\) 个区间，求最多能选出多少对区间，使得每对中的两个区间严格不交，一个区间至多属于一对区间，也可以不被选。
Solution
贪心。按左端点顺序遍历所有区间，开两个以右端点为关键字的小根堆，一个维护之前没有被匹配的区间，一个维护被匹配的区间对中右侧的那个区间，记当前区间为 \([l,r]\)，堆顶的区间为 \([l',r']\)。
- 如果没被匹配的区间堆顶 \(r'<l\)，那么就可以匹配，否则一定不存在未匹配的区间可以与之配。
- 如果被匹配的区间堆顶 \(r'<r\)，那么可以让当前区间去匹配堆顶原先匹配的区间，而将堆顶抽出来变为未匹配的，这样一定是更优的，并且由于我们是按左端点顺序遍历，\(l'<l\)，因此替换一定是合法的。
- 如果仍无法匹配，那就塞入未匹配的堆中。
代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=5e5+5;
int n,ans=0;
pii a[MAXN];
struct CMP{
bool operator ()(const pii& a,const pii& b){
return a.second>b.second;
}
};
priority_queue<pii,vector<pii>,CMP>match,unmatch;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].first>>a[i].second;
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
bool flag=0;
if(!unmatch.empty()){
auto it=unmatch.top();
if(it.second<a[i].first){
flag=1;
ans++;
unmatch.pop();
match.push(a[i]);
}
}
if(!flag && !match.empty()){
auto it=match.top();
if(it.second<a[i].second){
flag=1;
match.pop();
match.push(a[i]);
unmatch.push(it);
}
}
if(!flag){
unmatch.push(a[i]);
}
}
cout<<ans<<endl;
return 0;
}
T3 Codeforces Gym 102538H Horrible Cycles
Problem
有 \(2n\) 个点的二分图，左右各 \(n\) 个点，左侧第 \(i\) 个点与右侧第 \(j\in[1,a[i]]\) 个点有边，求图中有多少简单环（简单环：每个点只经过一次）。
Solution
将所有点重新排序，使得所有的左部点与它前面的所有右部点连边。
考虑到如果我们只保留 \(1\sim n\) 的点，环就会被拆成很多条链。
令 f[i][j] 为只从前 \(i\) 个点中选择点保留，形成了 \(j\) 条链的方案数，注意此时的链是钦定了顺序的链。
考虑转移：
- 如果点 \(i\) 是右部点，那么加入后不会产生任何边，如果选择它，就会形成一个新的链。
f[i][j]=f[i-1][j]+f[i-1][j-1]。 - 如果点 \(i\) 是左部点，那么加入后它会和前面所有右部点连边（这些边有些会被选入链中有些被弃用），如果选择它，就会将之前的链合并为一条，由于我们计数的是简单环，我们只能将当前点置于一条链中，相当于在 \(j\) 条链中分别选择一条与它的链尾相连，再选择一条与它的链头相连。
f[i][j]=f[i-1][j]+j*(j-1)*f[i-1][j+1]。
那么答案就是所有 \(i\) 的 f[i-1][1] 之和，表示 \(i\) 将这条链的两端连起来了，形成了一个环，并且要减去二元环数量 \(\sum a_i\)，最后还需要除以 \(2\)，因为链是有序的，每个环被算了两次。
由于每次状态转移只与上一次状态有关，可以压维。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN=5005;
const LL P=1e9+7;
inline LL qpow(LL a,LL b){
a%=P;
LL res=1;
while(b){
if(b&1) res=res*a%P;
a=a*a%P;
b/=2;
}
return res;
}
int n,a[MAXN];
LL ans=0,sum=0,f[MAXN];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
sum=(sum+(LL)a[i])%P;
}
sort(a+1,a+1+n);
f[0]=1;
for(int i=1;i<=n;i++){
for(int j=a[i-1]+1;j<=a[i];j++){
for(int k=j;k>=1;k--){
f[k]=(f[k]+f[k-1])%P;
}
}
ans=(ans+f[1])%P;
for(int j=1;j<=a[i];++j){
f[j-1]=(f[j-1]+1LL*j*((j-1+P)%P)%P*f[j]%P)%P;
}
}
ans=(ans-sum+P)%P;
cout<<ans*qpow(2,P-2)%P<<endl;
return 0;
}