我也不知道为什么就一道题
我们发现删除非常好删除，只要把自己和前驱后继形成的一个小三角形去掉，而插入要去找前驱和后继，所以考虑回滚莫队
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
inline int read()
{
int x=0;char ch,f=1;
for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
if(ch=='-') f=0,ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
const int N=2e5+10,cnt=350,p=998244353;
int n,m,k,sum;
int id[N],b[N],pre[N],suf[N];
int ans[N];
struct node
{
int x,y;
inline bool operator < (const node &t) const
{
return atan2(y,x)<atan2(t.y,t.x);
}
inline int operator * (const node &t) const
{
return x*t.y-y*t.x;
}
}a[N];
struct query
{
int l,r,id;
inline bool operator < (const query &t) const
{
return b[l]==b[t.l]?r>t.r:l<t.l;
}
}q[N];
inline bool cmp(int x,int y)
{
return a[x]<a[y];
}
inline void del(int x)
{
int l=pre[x],r=suf[x];
sum-=a[l]*a[x]+a[x]*a[r]-a[l]*a[r];
suf[l]=r,pre[r]=l;
}
inline void udel(int x)
{
int l=pre[x],r=suf[x];
sum+=a[l]*a[x]+a[x]*a[r]-a[l]*a[r];
suf[l]=pre[r]=x;
}
inline void main()
{
n=read(),m=read();
for(int i=1;i<=n;++i)
{
a[i].x=read(),a[i].y=read(),id[i]=i;
b[i]=(i-1)/cnt+1;
}
sort(id+1,id+n+1,cmp);id[0]=id[n];
for(int i=1;i<=n;++i)
{
pre[id[i]]=id[i-1],suf[id[i-1]]=id[i];
sum+=a[id[i-1]]*a[id[i]];
}
for(int i=1;i<=m;++i)
{
q[i].l=read(),q[i].r=read(),q[i].id=i;
}
sort(q+1,q+m+1);
for(int L=1,R,i=1,l=1,r=n;i<=m;L=R+1)
{
R=min(n,L+cnt-1);
for(;i<=m&&q[i].l<=R;++i)
{
for(;r>q[i].r;del(r--));
for(;l<q[i].l;del(l++));
ans[q[i].id]=sum;
for(;l>L;udel(--l));
}
for(;r<n;udel(++r));
for(;l<=R;del(l++));
}
for(int i=1;i<=m;printf("%lld
",ans[i++]));
}
}
signed main()
{
red::main();
return 0;
}