看到离线区间操作仍然考虑莫队，然后可以发现：我们对于原来的凸包集合按照极角序维护一个链表，那么删除一个位置可以\(O(1)\)，撤回删除操作也可以\(O(1)\)（因为原来的链表结构中当前节点就记录着其之前的前驱后继），但是动态加入操作至少要一个二分的\(log\)的复杂度。所以我们要尽可能避免动态加入。
因为没学过回滚莫队所以我的写法比较奇怪：设\(solve(l,r)\)表示正在解决左端点在块\(l\)内、右端点在块\(r\)内的询问，并且此时已经维护出块\(l\)左端点到块\(r\)的右端点的凸包链表并维护出答案。
此时对于左端点在块\(l\)内、右端点在块\(r\)内的询问，我们只需要把零散的部分减掉就可以得到答案，然后栈序撤销删除操作。
询问做完之后通过删除元素递归进\(solve(l+1,r)\)和\(solve(l,r-1)\)。记得重复的\(solve\)步骤不要做多遍。
#includeusing 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 longconst 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;}