【hdu 6089】Rikka with Terrorist

题意

　　有一个 \(n\times m\) 的二维网格，其中有 \(k\) 个禁止点。
　　有 \(q\) 组询问，每组询问为给一个点，求有多少个矩形以这个点为一角且不包含禁止点。
　　\(n,m,k,q\le 10^5\)

sol

　　zjt 是怎么认为这是道李超树题的……难道只是因为看到了官方题解吗？

　　这题不难，但是太恶心了我琢磨了三小时，关键是没人写题解，官方题解还写李超树误导人

#include<bits/stdc++.h>
#define ll long long
#define N 100010
#define lc o<<1
#define rc o<<1|1
#define fi first
#define se second
using namespace std;
typedef pair<ll,int> pr;
inline int read(){
   int x=0; bool f=1; char c=getchar();
   for(;!isdigit(c);c=getchar()) if(c=='-') f=0;
   for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
   if(f) return x;
   return 0-x;
}
int nn,mm,k,q;
struct Point{
   int x,y,id;
   Point(){}
   Point(int a, int b, int c):x(a), y(b), id(c){}
   inline bool operator < (const Point &a)const{
       return x!=a.x ? x<a.x : y<a.y;
   }
}a[N<<1];
namespace SegTree{
   struct Tree{int mx; ll sum;}tr[N<<2];
   void build(int o, int l, int r){
       tr[o].mx=tr[o].sum=0;
       if(l==r) return;
       int mid=l+r>>1;
       build(lc,l,mid), build(rc,mid+1,r);
   }
   ll go(int o, int l, int r,int v){
       if(l==r) return max(tr[o].mx,v);
       int mid=l+r>>1;
       if(tr[rc].mx>=v) return tr[o].sum-tr[rc].sum+go(rc,mid+1,r,v);
       else return go(lc,l,mid,v)+(ll)v*(r-mid);
   }
   inline void pushup(int o, int l, int r){
       int mid=l+r>>1;
       tr[o].sum = tr[rc].sum + go(lc,l,mid,tr[rc].mx);
       tr[o].mx = max(tr[lc].mx, tr[rc].mx);
   }
   void upd(int o, int l, int r, int x, int v){
       if(l==r){tr[o].mx=tr[o].sum=v; return;}
       int mid=l+r>>1;
       if(x<=mid) upd(lc,l,mid,x,v);
       else upd(rc,mid+1,r,x,v);
       pushup(o,l,r);
   }
   pr query(int o, int l, int r, int L, int R, int v){
       if(L<=l && r<=R) return pr(go(o,l,r,v), max(v,tr[o].mx));
       int mid=l+r>>1;
       if(R<=mid) return query(lc,l,mid,L,R,v);
       if(mid<L) return query(rc,mid+1,r,L,R,v);
       pr b = query(rc,mid+1,r,L,R,v);
       pr a = query(lc,l,mid,L,R,b.se);
       return pr(a.fi+b.fi, a.se);
   }
}using namespace SegTree;
void rotate(int n){
   for(int i=1; i<=n; ++i){
       int x=mm-a[i].y+1, y=a[i].x;
       a[i].x=x, a[i].y=y;
   }
   swap(nn,mm);
}
int now[N];
ll ans[N];
void solve(int n){
   rotate(n);
   build(1,1,mm);
   sort(a+1,a+n+1);
   memset(now,0,sizeof now);
   for(int i=1,lst=0; i<=n; i=lst+1){
       if(a[i].x!=a[i-1].x){
           lst=i;
           while(a[lst].x==a[lst+1].x) ++lst;
           int l=0;
           for(int j=i; j<=lst; ++j)
               if(!a[j].id) l=a[j].y;
               else if(l+1<=a[j].y-1)
                   ans[a[j].id] += (ll)a[j].x*(a[j].y-l-1) - query(1,1,mm,l+1,a[j].y-1,now[a[j].y]).fi;
           for(int j=i; j<=lst; ++j)
               if(!a[j].id)
                   upd(1,1,mm,a[j].y,a[j].x),
                   now[a[j].y]=a[j].x;
       }
   }
}
int main(){
   nn=read(), mm=read(), k=read(), q=read();
   int x,y;
   for(int i=1; i<=k; ++i){
       x=read(), y=read();
       a[i]=Point(x,y,0);
   }
   for(int i=1; i<=q; ++i){
       x=read(), y=read();
       a[k+i]=Point(x,y,i);
   }
   for(int i=1; i<=4; ++i) solve(k+q);
   for(int i=1; i<=q; ++i) printf("%lld\n",ans[i]+1);
   return 0;
}
/*
19 19 20 19

9 11
12 11
8 3
10 2
11 2
18 8
10 6
16 11
13 9
13 8
8 7
2 6
5 7
7 18
6 5
16 15
17 14
15 1
2 4
3 3

10 10
15 17
8 17
6 9
16 2
5 15
17 4
4 3
4 14
9 6
19 16
14 4
7 11
14 15
4 1
14 14
3 11
9 19
15 15
*/

【hdu 6089】Rikka with Terrorist

原文：https://www.cnblogs.com/scx2015noip-as-php/p/hdu6089.html