第二章营销型网站建设测验,广告平面设计师的工作内容,WordPress三栏资讯主题,dede门户网站模板下载感觉像是之前做过的题的加强版#x1f605;
考虑容斥哪些区间不合法。直接处理比较困难#xff0c;考虑将所有区间按右端点排序#xff0c;并将端点离散化#xff08;将右端点 1 1 1#xff0c;转化为左闭右开区间#xff09;#xff0c;设 d p i , j , k dp_{i,j,k} …感觉像是之前做过的题的加强版
考虑容斥哪些区间不合法。直接处理比较困难考虑将所有区间按右端点排序并将端点离散化将右端点 1 1 1转化为左闭右开区间设 d p i , j , k dp_{i,j,k} dpi,j,k表示只考虑前 i i i个区间以及 [ 1 , j ) [1,j) [1,j)这段前缀上一个选择的区间类型是 k ∈ [ 0 , 1 ] k\in [0,1] k∈[0,1]时的答案。转移如下 d p i , j , k ← d p i − 1 , j , k dp_{i,j,k}\gets dp_{i-1,j,k} dpi,j,k←dpi−1,j,k d p i , j , k ′ ← − d p i − 1 , l i , k × 1 2 r i − l i dp_{i,j,k}\gets -dp_{i-1,l_i,k}\times \frac{1}{2^{r_i-l_i}} dpi,j,k′←−dpi−1,li,k×2ri−li1条件 r i ≤ j r_i\le j ri≤j可以是相同类型的区间也可以是不同类型的区间 d p i , j , k ← − d p i − 1 , j , k dp_{i,j,k}\gets -dp_{i-1,j,k} dpi,j,k←−dpi−1,j,k条件 l i ≥ j l_i\ge j li≥j且必须是相同类型区间 d p i , j , k ← − d p i − 1 , l i , k × 1 2 j − l i dp_{i,j,k}\gets -dp_{i-1,l_i,k}\times \frac{1}{2^{j-l_i}} dpi,j,k←−dpi−1,li,k×2j−li1条件 l i j r i l_ij r_i lijri且必须是相同类型区间
最后答案要乘上 2 K 2^K 2K。
显然这些操作都可以用线段树去维护。
有没有更好的方法
注意到第三种转移加上第一种转移是将 ≤ l i \le l_i ≤li的 D P DP DP值推平成 0 0 0那么我们维护一个指针 p p p表示 [ 1 , p ] [1,p] [1,p]这段前缀的 D P DP DP值都是 0 0 0如果 l i ≤ p l_i\le p li≤p那么什么都不做否则我们暴力将指针移动到 l i l_i li然后根据转移的范围在差分数组上打标记即可。
复杂度 O ( n log n ) O(n\log n) O(nlogn)。 remark \text{remark} remark 我低估了这道题的思维难度。。。主要是后半部分
#includebits/stdc.h
#define ll long long
#define pb push_back
#define inf 0x3f3f3f3f
#define fi first
#define se second
using namespace std;
const int N4e55;
const int mod1e97;
int n,m,K,lsh[N1],cnt;
struct node{int l,r,t;bool operator (const node a)const{return ra.r;}
}a[N];
ll fpow(ll x,ll ymod-2){ll z(1);for(;y;y1){if(y1)zz*x%mod;xx*x%mod;}return z;
}
int get(int x){return lower_bound(lsh1,lsh1cnt,x)-lsh;
}
int p[2];
ll c[2][N][2];
void add(ll x,ll y){x(xy)%mod;
}
ll calc(int f,int x){return (c[f][x][0]c[f][x][1]*fpow(mod11,lsh[x]))%mod;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinKnm;for(int i1;inm;i){cina[i].la[i].r,a[i].r,a[i].t(in);lsh[cnt]a[i].l,lsh[cnt]a[i].r;}sort(lsh1,lsh1cnt),cntunique(lsh1,lsh1cnt)-lsh-1;nm;for(int i1;in;i)a[i].lget(a[i].l),a[i].rget(a[i].r);sort(a1,a1n);c[0][1][0]c[1][1][0]1;ll res1;for(int i1;in;i){int la[i].l,ra[i].r,fa[i].t;if(p[f]l)continue;while(p[f]l){add(c[f][p[f]1][0],c[f][p[f]][0]);add(c[f][p[f]1][1],c[f][p[f]][1]);p[f];}ll xcalc(f,l),y-x*fpow(mod11,lsh[r]-lsh[l])%mod;add(res,y);add(c[f^1][r][0],y);add(c[f][r][0],y);add(c[f][l1][1],-x*fpow(2,lsh[l]));add(c[f][r][1],x*fpow(2,lsh[l]));}resres*fpow(2,K)%mod;cout(resmod)%mod;
}
