本文共 3091 字，大约阅读时间需要 10 分钟。

和前面一样只不过rank变成了sum

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;char c;bool flag;inline void read(int &a){a=0;do c=getchar();while(c!='-'&&(c<'0'||c>'9'));if(c=='-')flag=true,c=getchar();while(c<='9'&&c>='0')a=(a<<3)+(a<<1)+c-'0',c=getchar();if(flag)a=-a,flag=false;}struct P{ int x,y,data;};struct Node{Node *f,*lc,*rc;int sum,data;double Key;inline bool l(){ return f->lc==this;}}*Empty;Node *Stack[100001],Ce[100001];int Tot;inline void Bg(){Empty=new Node;Empty->lc=Empty->rc=Empty->f=Empty;Empty->sum=Empty->data=0;for(int i=0;i<=100000;i++)Stack[i]=Ce+i;Tot=100000;}inline Node*New(){Node *R=Stack[Tot--];R->lc=R->rc=Empty;R->f=R;R->sum=R->data=0;return R;}inline void*Del(Node *E){Stack[++Tot]=E;}inline void updata(Node *a){a->sum=a->lc->sum+a->rc->sum+a->data;}inline void Lc(Node *a){ Node *f; if(a->f->f==a->f)f=a; else if(a->f->l())f=a->f->f,f->lc=a; else f=a->f->f,f->rc=a; a->f->lc=a->rc; a->rc->f=a->f; a->rc=a->f; a->f->f=a; a->f=f; updata(a->rc);}inline void Rc(Node *a){ Node *f; if(a->f->f==a->f)f=a; else if(a->f->l())f=a->f->f,f->lc=a; else f=a->f->f,f->rc=a; a->f->rc=a->lc; a->lc->f=a->f; a->lc=a->f; a->f->f=a; a->f=f; updata(a->lc);}inline void On(Node *a){a->l()?Lc(a):Rc(a);}inline void Twi(Node *a){a->l()==a->f->l()?On(a->f):On(a);On(a);}inline void Splay(Node *a){ while(a->f->f!=a->f)Twi(a);while(a->f!=a)On(a);updata(a);}inline P operator -(P a,P b){ return (P){a.x-b.x,a.y-b.y};}inline int operator *(P a,P b){ return a.x*b.y-b.x*a.y;}int tmp=0;inline void Insert(Node *Cur,Node *C){ if(C->Key
         
          Key) if(Cur->lc==Empty){Cur->lc=C,C->f=Cur;} else Insert(Cur->lc,C); else if(Cur->rc==Empty){tmp+=Cur->lc->sum+Cur->data;Cur->rc=C,C->f=Cur;} else tmp+=Cur->lc->sum+Cur->data,Insert(Cur->rc,C); updata(Cur);};P Std;double Key[3001];inline double Atan2(P a){ return atan2(a.y,a.x);}P L[30001];int Val[300001];int no[10001],non[10001];inline bool cmp(int a,int b){ return Key[a]>Key[b];}int f[2301][2301];int n;void Dl(Node *R){ if(R==Empty)return ; Dl(R->lc),Dl(R->rc);Del(R);}inline void Pre(){ Std=(P){-84221,-72421}; for(int i=1;i<=n;i++) Key[i]=Atan2(L[i]-Std),no[i]=i; sort(no+1,no+n+1,cmp); for(int i=1;i<=n;i++)non[no[i]]=i; for(int i=1;i
          
           Key=Atan2(L[no[i+1]]-Std); R->data=Val[no[i+1]]; R->f=R; updata(R); for(int j=i+2;j<=n;j++) { tmp=0; Node *RR=New(); RR->Key=Atan2(L[no[j]]-Std); RR->data=Val[no[j]]; updata(RR); Insert(R,RR); f[i][j]=f[j][i]=tmp;// if(rand()&7==7)Splay(RR),R=RR; } Dl(R); }}int Cache[100001];inline void Get(){ Std=(P){-84221,-72421}; int s; read(s); for(int i=1;i<=s;i++)read(Cache[i]); Cache[s+1]=Cache[1]; int A,sum=0,tp=0; for(int i=1;i<=s;i++) { if((L[Cache[i]]-Std)*(L[Cache[i+1]]-Std)<0) sum-=f[non[Cache[i]]][non[Cache[i+1]]]; else sum+=f[non[Cache[i]]][non[Cache[i+1]]]; } if(sum<0)sum=-sum; printf("%d\n",sum);}int m,q;int main(){ Bg(); read(n); read(m); for(int i=1;i<=n;i++)read(L[i].x),read(L[i].y); for(int i=1;i<=m;i++)read(L[n+i].x),read(L[n+i].y),read(Val[n+i]); n+=m; Pre(); read(q); while(q--) Get(); return 0;}