Codeforces 453E - Little Pony and Lord Tirek（二维线段树+ODT）

一道难度 *3100 的 DS，而且被我自己搞出来了！

不过我终究还是技不如人，因为这是一个 \(n\log^2n\) + 大常数的辣鸡做法，几乎是卡着时空限制过去的……

首先注意到对于每个小马，在任意时刻它的法力值只有三种可能：

\(s_i+kr_i(k\in\mathbb{Z})\)
\(kr_i(k\in\mathbb{Z})\)
\(m_i\)

我们考虑对这三种情况一一分析，对于第一种情况这里的 \(k\) 只可能等于我们待查询的 \(t\)，并且这种情况可能发生当且仅当 \(i\) 没有被清空过，并且 \(s_i+kr_i\le m_i\)，第二个条件好办，我们如果设 \(a_i=\lfloor\dfrac{m_i-s_i}{r_i}\rfloor\)（如果 \(r_i=0\) 那么 \(a_i=\infty\)），那么 \(i\) 符合第二个条件当且仅当 \(a_i\ge t\)，第一个条件虽然看起来棘手，但是我们可以维护一个 set 表示没有被清空过的集合，每次进行查询操作就将这个 set 中属于 \([l,r]\) 的元素全部删除，不难发现每个数最多被删除一次，因此复杂度是 \(n\log n\) 的。接下来问题就转化为如何维护这个值，显然它可以转化为 \(\sum\limits_{i=l}^r[a_i\ge t]s_i+t\sum\limits_{i=l}^r[a_i\ge t]r_i\)，两部分结构类似，因此维护方法也类似，注意到这里涉及两维，\(i\in[l,r]\) 和 \(a_i\ge t\)，那么该操作相当于查询矩形 \((l,a_i),(r,\infty)\) 中权值的和，这个离散化+建立二维线段树就可以搞定了，具体来说先将所有 \((i,a_i)\) 看作一个点并更新其在二维线段树上的权值，每次我们将一个数从 set 中删除就将对应的 \((i,a_i)\) 的贡献撤销掉，正确性显然。

搞清楚这个情况后，我们也可以顺带着把 \(i\) 没有被清空过的贡献都搞清楚，若 \(i\) 没有被清空过，可以分两种情况，\(a_i\ge t\) 那么贡献为 \(s_i+tr_i\)，这个刚刚已经探究过了，\(a_i<t\) 那么贡献为 \(m_i\)，不难发现这个也可以写成矩形和的形式，同样二维线段树维护即可，这里就不再赘述了。

\(i\) 没有被清空过的情况搞清楚了，接下来考虑 \(i\) 被清空过的情况，显然对于一个被清空过的 \(i\) 它都有一个上次被清空的时间 \(T_i\)，在这 \(t-T_i\) 分钟内它的法力值最多可以上涨 \(r_i(t-T_i)\)，那么它的贡献就是 \(\min(m_i,r_i(t-T_i))\)，还是按照之前的套路，记 \(b_i=\lfloor\dfrac{m_i}{r_i}\rfloor\)，还是分两种情况，若 \(b_i\ge t-T_i\)，那么贡献为 \(r_i(t-T_i)\)，否则贡献为 \(m_i\)，这样还是不好做，因为这里的 \(T_i\) 都是互不相同的，无法直接维护。不过不难发现一个性质，那就是任意时刻 \(T_i\) 都是成段分布的，也就是说相同的 \(T_i\) 都是一段一段的，我们记三元组 \((l,r,t)\) 表示 \(\forall i\in[l,r],T_i=t\)，我们考虑开一个 set 维护所有三元组并对每个三元组计算贡献——这个就可以按照上面的套路二维线段树了，相信如果理解了前面的部分那这边应该的相当容易的。我们还可以发现所有计算过贡献的三元组 \((l',r',t')\) 必定满足 \(l\le l'\le r'\le r\)，这样的三元组在查询过后都会从 set 中删除，标准的 ODT 模型，按照 P4690 [Ynoi2016] 镜中的昆虫的套路维护即可。

时间复杂度 \(n\log^2n\)，由于要维护五个二维线段树，常数巨大，但还好卡过去了（（（

最后说一句，wtm 不是 sb，又拿未去重的数组离散化，话说恰好一年前的今天也犯过这个错误来着的？

const int MAXN=1e5;

const int MAXP=MAXN*20;

const int INF=0x3f3f3f3f;

int n,s[MAXN+5],r[MAXN+5],mx[MAXN+5],lim1[MAXN+5],lim2[MAXN+5];

int key1[MAXN+5],key2[MAXN+5],uni1[MAXN+5],uni2[MAXN+5],num1=0,num2=0;

struct seg2d{

	struct node{int ch[2];ll sum;} s[MAXP+5];

	int rt[MAXN+5],ncnt;

	seg2d(){ncnt=0;memset(rt,0,sizeof(rt));}

	void add_in(int &k,int l,int r,int x,int v){

		if(!k) k=++ncnt;s[k].sum+=v;

		if(l==r) return;int mid=l+r>>1;

		if(x<=mid) add_in(s[k].ch[0],l,mid,x,v);

		else add_in(s[k].ch[1],mid+1,r,x,v);

	}

	ll query_in(int k,int l,int r,int ql,int qr){

		if(ql>qr||!k) return 0;int mid=l+r>>1;

		if(ql<=l&&r<=qr) return s[k].sum;

		if(qr<=mid) return query_in(s[k].ch[0],l,mid,ql,qr);

		else if(ql>mid) return query_in(s[k].ch[1],mid+1,r,ql,qr);

		else return query_in(s[k].ch[0],l,mid,ql,mid)+query_in(s[k].ch[1],mid+1,r,mid+1,qr);

	}

	void add_out(int x,int p,int v){

		for(int i=x;i<=n;i+=(i&(-i))) add_in(rt[i],1,max(num1,num2),p,v);

	}

	ll query_out(int x,int l,int r){

		ll ret=0;

		for(int i=x;i;i&=(i-1)) ret+=query_in(rt[i],1,max(num1,num2),l,r);

		return ret;

	}

	ll query(int l1,int r1,int l2,int r2){return query_out(r1,l2,r2)-query_out(l1-1,l2,r2);}

} t_s,t_r,t_m,T_r,T_m;

set<int> fst;

struct event{

	int l,r,t;

	event(int _l=0,int _r=0,int _t=0):l(_l),r(_r),t(_t){}

	bool operator <(const event &rhs) const{return l<rhs.l;}

};

set<event> st;

void split(int x){

	if(st.empty()) return;

	set<event>::iterator it=st.lower_bound(event(x+1,0,0));

	if(it==st.begin()) return;

	--it;event val=*it;if(val.r<=x) return;

	st.erase(st.find(val));

	st.insert(event(val.l,x,val.t));

	st.insert(event(x+1,val.r,val.t));

}

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%d%d%d",&s[i],&mx[i],&r[i]);

	for(int i=1;i<=n;i++){

		if(r[i]){

			lim1[i]=mx[i]/r[i];

			lim2[i]=(mx[i]-s[i])/r[i];

		} else lim1[i]=lim2[i]=INF;

	}

	for(int i=1;i<=n;i++) key1[i]=lim1[i],key2[i]=lim2[i];

	sort(key1+1,key1+n+1);sort(key2+1,key2+n+1);key1[0]=-INF;key2[0]=-INF;

	for(int i=1;i<=n;i++) if(key1[i-1]!=key1[i]) uni1[++num1]=key1[i];

	for(int i=1;i<=n;i++) if(key2[i-1]!=key2[i]) uni2[++num2]=key2[i];

	for(int i=1;i<=n;i++){

		lim1[i]=lower_bound(uni1+1,uni1+num1+1,lim1[i])-uni1;//remember to unique

		lim2[i]=lower_bound(uni2+1,uni2+num2+1,lim2[i])-uni2;

//		printf("%d %d\n",lim1[i],lim2[i]);

	}

	for(int i=1;i<=n;i++) fst.insert(i);

	for(int i=1;i<=n;i++){

		t_s.add_out(i,lim2[i],s[i]);

		t_r.add_out(i,lim2[i],r[i]);

		t_m.add_out(i,lim2[i],mx[i]);

	} int qu;scanf("%d",&qu);

	while(qu--){

		int t,L,R;scanf("%d%d%d",&t,&L,&R);

		int pos=lower_bound(uni2+1,uni2+num2+1,t)-uni2;

		ll sums=t_s.query(L,R,pos,num2);

		ll sumr=t_r.query(L,R,pos,num2);

		ll summ=t_m.query(L,R,1,pos-1);

//		printf("%d %lld %lld %lld\n",pos,sums,sumr,summ);

//		printf("%lld\n",summ+sums+sumr*t);

		ll sum=summ+sums+sumr*t;

		if(L!=1) split(L-1);split(R);

		while(1){

			set<event>::iterator it=st.lower_bound(event(L,0,0));

			if(it==st.end()||(it->l)>R) break;event val=*it;

			int pp=lower_bound(uni1+1,uni1+num1+1,t-val.t)-uni1;

			ll ssumr=T_r.query(val.l,val.r,pp,num1);

			ll ssumm=T_m.query(val.l,val.r,1,pp-1);

//			printf("%d %d %d %d\n",val.l,val.r,t-val.t,pp);

//			printf("%lld %lld\n",ssumr,ssumm);

			sum+=ssumm+ssumr*(t-val.t);st.erase(st.find(val));

		} st.insert(event(L,R,t));

		while(1){

			set<int>::iterator it=fst.lower_bound(L);

			if(it==fst.end()||(*it)>R) break;

			int x=(*it);

			t_s.add_out(x,lim2[x],-s[x]);

			t_r.add_out(x,lim2[x],-r[x]);

			t_m.add_out(x,lim2[x],-mx[x]);

			T_r.add_out(x,lim1[x],r[x]);

			T_m.add_out(x,lim1[x],mx[x]);

			fst.erase(fst.find(x));

		} printf("%lld\n",sum);

	}

	return 0;

}

/*

10

0 4 2

0 3 0

0 96 7

0 25 9

0 90 4

0 93 5

0 87 3

0 58 3

0 65 8

0 30 0

10

3 3 4

10 1 7

11 8 9

19 4 9

28 3 10

33 5 10

38 4 5

45 5 7

48 5 9

58 1 4

*/

巴特西

Codeforces 453E - Little Pony and Lord Tirek（二维线段树+ODT）

最新文章

热门文章