「雅礼集训 2018 Day5」Convex 凸包、莫队

LOJ

看到离线区间操作仍然考虑莫队，然后可以发现：我们对于原来的凸包集合按照极角序维护一个链表，那么删除一个位置可以\(O(1)\)，撤回删除操作也可以\(O(1)\)（因为原来的链表结构中当前节点就记录着其之前的前驱后继），但是动态加入操作至少要一个二分的\(log\)的复杂度。所以我们要尽可能避免动态加入。

因为没学过回滚莫队所以我的写法比较奇怪：设\(solve(l,r)\)表示正在解决左端点在块\(l\)内、右端点在块\(r\)内的询问，并且此时已经维护出块\(l\)左端点到块\(r\)的右端点的凸包链表并维护出答案。

此时对于左端点在块\(l\)内、右端点在块\(r\)内的询问，我们只需要把零散的部分减掉就可以得到答案，然后栈序撤销删除操作。

询问做完之后通过删除元素递归进\(solve(l+1,r)\)和\(solve(l,r-1)\)。记得重复的\(solve\)步骤不要做多遍。

#include<bits/stdc++.h>

using namespace std;

int read(){

	int a = 0; char c = getchar(); bool f = 0;

	while(!isdigit(c)){f = c == '-'; c = getchar();}

	while(isdigit(c)){

		a = a * 10 + c - 48; c = getchar();

	}

	return f ? -a : a;

}

#define int long long

const int _ = 1.5e5 + 7 , T = sqrt(_) + 10;

struct node{int P , S;}now[_]; struct query{int l , r , id;};

#define PII pair < int , int >

int N , M , id[_] , ans[_] , S; vector < query > qry[T][T];

PII pos[_]; long double ang[_]; bool vis[T][T];

int operator %(PII A , PII B){return A.first * B.second - A.second * B.first;}

int cnt = 0;

void del(int x){

	++cnt;

	S = S - pos[x] % pos[now[x].S] - pos[now[x].P] % pos[x] + pos[now[x].P] % pos[now[x].S];

	now[now[x].P].S = now[x].S; now[now[x].S].P = now[x].P;

}

void add(int x){

	++cnt;

	S = S - pos[now[x].P] % pos[now[x].S] + pos[now[x].P] % pos[x] + pos[x] % pos[now[x].S];

	now[now[x].P].S = x; now[now[x].S].P = x;

}

void solve(int l , int r){

	//cerr << l << ' ' << r << endl;

	if(vis[l / T][r / T]) return;

	vis[l / T][r / T] = 1;

	for(auto t : qry[l / T][r / T]){

		assert(t.l - l <= T && r - t.r <= T);

		for(int i = l ; i < t.l ; ++i) del(i);

		for(int i = r ; i > t.r ; --i) del(i);

		ans[t.id] = S;

		for(int i = t.r + 1 ; i <= r ; ++i) add(i);

		for(int i = t.l - 1 ; i >= l ; --i) add(i);

	}

	if(r - l > T){

		int cur = l; do{del(l++);}while(l % T); solve(l , r); do{add(--l);}while(l != cur);

		cur = r; do{del(r--);}while((r + 1) % T); solve(l , r); do{add(++r);}while(r != cur);

	}

}

signed main(){

	N = read(); M = read();

	for(int i = 0 ; i < N ; ++i){

		pos[i].first = read(); pos[i].second = read();

		id[i] = i; ang[i] = atan2(pos[i].second , pos[i].first);

	}

	sort(id , id + N , [&](int x , int y){return ang[x] < ang[y];});

	for(int i = 0 ; i < N ; ++i){now[id[i]].P = id[i ? i - 1 : N - 1]; now[id[i]].S = id[i == N - 1 ? 0 : i + 1];}

	for(int i = 1 ; i <= M ; ++i){int p = read() - 1 , q = read() - 1; qry[p / T][q / T].push_back((query){p , q , i});}

	for(int i = 0 ; i < N ; ++i){S += pos[i] % pos[now[i].S];}

	solve(0 , N - 1); for(int i = 1 ; i <= M ; ++i) printf("%lld\n" , ans[i]);

	cerr << cnt << endl;

	return 0;

}

巴特西

「雅礼集训 2018 Day5」Convex 凸包、莫队

最新文章

热门文章