鉴于我之前每次考试计数问题都会错一大堆, 所以我滚过来写总结了
先膜拜贡献了这个题单的@feecle6418
以下题目笔者没有事先做过, 和大家一起做, 所以会有一些不成熟的思路, 但是同时也会更好的展示思维路径.
我们先来看几道题来醒醒脑子
洛谷 P6146 Help Yourself G
题意简述:
现在有 $n (n \le 10 ^ 5) $ 条线段, 对于每一个线段的组合, 我们令他产生的连通块数量为他的复杂度, 求所有组合的复杂度之和
(可能不清楚, 左边题目右边博客效果更佳)
首先一个很典的设计是令 \(f_i\) 表示考虑了前 \(i\) 条线段的复杂度, 考虑转移. 我也知道要转移啊
我们思考, 什么时候新加入的这个线段会对答案产生贡献.
思考一下, 一会儿再看答案
首先, 每一个之前的方案都会和这个产生一个组合, ans翻倍
没错, 就是当一个方案与这个线段没有交点的时候.
我们去统计在这之前和自己没有交集的线段数目, 那么这个线段对答案额外贡献就是 \(2 ^ n\)
(每个都可以选或不选, 都不选也是一种方案)
那么我们先将线段离散, 然后线段树维护即可.
具体的, 我们先把所有的线段按照左端点排序, 然后我们只需要统计右端点小于自己的即可.
时间复杂度\(O(n \log n)\)
代码:
//start at 15:38
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MAXN = 2e5 + 10;
const ll MOD = 1e9 + 7;
ll N;
struct xd{
int l, r;
}xs[MAXN];
ll qp(ll d, ll c){
//cerr << d << " " << c << "\n";
ll ans = 1;
while(c){
if(c & 1) ans = (ans * d) % MOD;
d = (d * d) % MOD;
c >>= 1;
}
return ans;
}
ll t[MAXN][3];
inline ll lowbit(ll x){return x & -x;}
inline void add(ll p, ll v, ll f){
for(; p <= 2 * N; p += lowbit(p)) t[p][f] += v;
}
inline ll fin(ll p, ll f){
if(p <= 0) return 0;
ll sum = 0;
for(; p; p -= lowbit(p)) sum += t[p][f];
return sum;
}
inline ll fi(ll l, ll r, ll f){ return fin(r, f) - fin(l - 1, f);}
ll ans;
bool cmp(xd a, xd b){return a.l < b.l;}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> N;
for(int i = 1; i <= N; i++) cin >> xs[i].l >> xs[i].r;
sort(xs + 1, xs + N + 1, cmp);
for(int i = 1; i <= N; i++){
ll n = fi(1, xs[i].l - 1, 1);
//cerr << n << "\n";
//cerr << n << " " << fi(1, l[i] - 1, 2) << " " << fi(r[i] + 1, 2 * N, 1) << "\n";
ans = (ans * 2 + qp(2, n)) % MOD;
add(xs[i].r, 1, 1);
}
cout << ans << "\n";
}
//end at 16:06
推题+代码将近一个小时, 还是太菜了