题目链接
题意&＃xff1a;n个人排成一列&＃xff0c;一开始他们互不认识&＃xff0c;每次选[l,r]上的人开party&＃xff0c;使他们互相认识&＃xff0c;求出每次party之后新互相认识的人的对数。
思路&＃xff1a;把“互相认识”变成单向连边&＃xff0c;只考虑左边的人对右边的贡献。对于每个人&＃xff0c;他认识的人的区间必然是连续的&＃xff0c;可以维护他认识的最右边的人R&＃xff0c;这样更新操作相当于把[l,r]所有人的R值变成max(R,r)&＃xff0c;可以构造线段树维护每个区间中R的最小值mi&＃xff0c;如果最小值大于等于R的话就不用更新了&＃xff0c;直接退出&＃xff0c;否则暴力修改每个点的值。
先上个假算法&＃xff1a;
1 #include
2 using namespace std;
3 typedef long long ll;
4 const int N&＃61;5e5&＃43;10,inf&＃61;0x3f3f3f3f;
5 #define ls (u<<1)
6 #define rs (u<<1|1)
7 #define mid ((l&＃43;r)>>1)
8 int mi[N<<2],n,m;
9 ll ans;
10 void pu(int u) {mi[u]&＃61;min(mi[ls],mi[rs]);}
11 void build(int u&＃61;1,int l&＃61;1,int r&＃61;n) {
12 if(l&＃61;&＃61;r) {mi[u]&＃61;l; return;}
13 build(ls,l,mid),build(rs,mid&＃43;1,r),pu(u);
14 }
15 void upd(int L,int R,int u&＃61;1,int l&＃61;1,int r&＃61;n) {
16 if(l>R||r
17 if(l&＃61;&＃61;r) {ans&＃43;&＃61;R-mi[u],mi[u]&＃61;R; return;}
18 upd(L,R,ls,l,mid),upd(L,R,rs,mid&＃43;1,r),pu(u);
19 }
20 int main() {
21 while(scanf("%d%d",&n,&m)&＃61;&＃61;2) {
22 build();
23 while(m--) {
24 ans&＃61;0;
25 int l,r;
26 scanf("%d%d",&l,&r);
27 upd(l,r);
28 printf("%lld\n",ans);
29 }
30 }
31 return 0;
32 }
这个算法本身是没有问题的&＃xff0c;交上去也能AC&＃xff0c;但会被一些极端的数据卡死&＃xff0c;比如[1,1],[1,2],...,[1,n]这样的&＃xff0c;会被卡成n^2&＃xff0c;因此可以加一些优化。
由于每个人认识的最右边的人R的值是非递减的&＃xff0c;即任意i>j&＃xff0c;R[i]>&＃61;R[j]&＃xff0c;因此每次发生变化的区间必然是连续的&＃xff0c;可以把单点修改换成区间修改&＃xff0c;这样就不会被卡了。
1 #include
2 using namespace std;
3 typedef long long ll;
4 const int N&＃61;5e5&＃43;10,inf&＃61;0x3f3f3f3f;
5 #define ls (u<<1)
6 #define rs (u<<1|1)
7 #define mid ((l&＃43;r)>>1)
8 int mx[N<<2],mi[N<<2],lz[N<<2],n,m;
9 ll sum[N<<2],ans;
10 void pu(int u) {
11 mi[u]&＃61;min(mi[ls],mi[rs]);
12 mx[u]&＃61;max(mx[ls],mx[rs]);
13 sum[u]&＃61;sum[ls]&＃43;sum[rs];
14 }
15 void pd(int u,int l,int r) {
16 if(lz[u]) {
17 sum[ls]&＃61;(ll)lz[u]*(mid-l&＃43;1),sum[rs]&＃61;(ll)lz[u]*(r-mid);
18 mi[ls]&＃61;mi[rs]&＃61;mx[ls]&＃61;mx[rs]&＃61;lz[ls]&＃61;lz[rs]&＃61;lz[u],lz[u]&＃61;0;
19 }
20 }
21 void build(int u&＃61;1,int l&＃61;1,int r&＃61;n) {
22 lz[u]&＃61;0;
23 if(l&＃61;&＃61;r) {sum[u]&＃61;mi[u]&＃61;mx[u]&＃61;l; return;}
24 build(ls,l,mid),build(rs,mid&＃43;1,r),pu(u);
25 }
26 void upd(int L,int R,int u&＃61;1,int l&＃61;1,int r&＃61;n) {
27 if(l>R||r
28 if(l>&＃61;L&&r<&＃61;R&&mx[u]<&＃61;R) {sum[u]&＃61;(ll)R*(r-l&＃43;1),mi[u]&＃61;mx[u]&＃61;lz[u]&＃61;R; return;}
29 pd(u,l,r);
30 upd(L,R,ls,l,mid),upd(L,R,rs,mid&＃43;1,r),pu(u);
31 }
32 int main() {
33 while(scanf("%d%d",&n,&m)&＃61;&＃61;2) {
34 build(),ans&＃61;sum[1];
35 while(m--) {
36 int l,r;
37 scanf("%d%d",&l,&r);
38 upd(l,r);
39 printf("%lld\n",sum[1]-ans);
40 ans&＃61;sum[1];
41 }
42 }
43 return 0;
44 }
然后据说还有一种叫“吉司机线段树”的东西也能做&＃xff1f;赶紧学了学(便乘)&＃xff0c;感觉对于区间取max/min这类问题的处理强大的&＃xff0c;普适性也比较高。
对于区间取max操作&＃xff0c;其基本思想是维护区间和sum,区间最小值mi,区间次小值se以及区间最小值个数nmi。如果要对[l,r]上的所有数与x取max&＃xff0c;那么分三种情况讨论即可&＃xff1a;
1)若x<&＃61;mi&＃xff0c;则修改操作无效&＃xff0c;退出
2)若mi 3)若x>&＃61;se&＃xff0c;则在左右区间递归进行下去 1 #include
2 using namespace std;
3 typedef long long ll;
4 const int N&＃61;5e5&＃43;10,inf&＃61;0x3f3f3f3f;
5 #define ls (u<<1)
6 #define rs (u<<1|1)
7 #define mid ((l&＃43;r)>>1)
8 int mi[N<<2],nmi[N<<2],se[N<<2],lz[N<<2],n,m;
9 ll sum[N<<2],ans;
10 void pu(int u) {
11 sum[u]&＃61;sum[ls]&＃43;sum[rs];
12 mi[u]&＃61;min(mi[ls],mi[rs]),se[u]&＃61;max(mi[ls],mi[rs]);
13 se[u]&＃61;se[u]&＃61;&＃61;mi[u]?min(se[ls],se[rs]):min(se[u],min(se[ls],se[rs]));
14 nmi[u]&＃61;(mi[ls]&＃61;&＃61;mi[u]?nmi[ls]:0)&＃43;(mi[rs]&＃61;&＃61;mi[u]?nmi[rs]:0);
15 }
16 void change(int u,int x) {sum[u]&＃43;&＃61;(ll)nmi[u]*(x-mi[u]),mi[u]&＃61;lz[u]&＃61;x;}
17 void pd(int u) {
18 if(~lz[u]) {
19 if(mi[ls]<lz[u])change(ls,lz[u]);
20 if(mi[rs]<lz[u])change(rs,lz[u]);
21 lz[u]&＃61;-1;
22 }
23 }
24 void build(int u&＃61;1,int l&＃61;1,int r&＃61;n) {
25 lz[u]&＃61;-1;
26 if(l&＃61;&＃61;r) {sum[u]&＃61;mi[u]&＃61;l,nmi[u]&＃61;1,se[u]&＃61;inf; return;}
27 build(ls,l,mid),build(rs,mid&＃43;1,r),pu(u);
28 }
29 void upd(int L,int R,int x,int u&＃61;1,int l&＃61;1,int r&＃61;n) {
30 if(l>R||r
31 if(l>&＃61;L&&r<&＃61;R&&x
32 pd(u),upd(L,R,x,ls,l,mid),upd(L,R,x,rs,mid&＃43;1,r),pu(u);
33 }
34 int main() {
35 while(scanf("%d%d",&n,&m)&＃61;&＃61;2) {
36 build(),ans&＃61;sum[1];
37 while(m--) {
38 int l,r;
39 scanf("%d%d",&l,&r);
40 upd(l,r,r);
41 printf("%lld\n",sum[1]-ans);
42 ans&＃61;sum[1];
43 }
44 }
45 return 0;
46 }
