P4169 [Violet]天使玩偶/SJY摆棋子

  1 // luogu-judger-enable-o2
  2 #include<cstdio> 
  3 #include<iostream>
  4 using namespace std;
  5 const int maxn=1e7+10;
  6 const int inf=2e7+7;
  7 struct node
  8 {
  9     int x,y,id,ans,time;
 10 }a[maxn],b[maxn],tt[maxn];;
 11 int flag;
 12 int len,x,y;
 13 int n,q;
 14 struct XX
 15 {
 16     int c[maxn];
 17     int  lowbit(int x)
 18     {
 19         return x&(-x);
 20     }
 21     void update(int x,int w)
 22     {
 23         for(;x<=len;x+=lowbit(x))
 24         {
 25             c[x]=max(w,c[x]);
 26         }
 27     }
 28     int sum(int x)
 29     {
 30         int res=0;
 31         for(;x;x-=lowbit(x))
 32         {
 33             res=max(res,c[x]);
 34         }
 35         if(res)
 36         {
 37             return res;
 38         }
 39         else
 40         return -inf;
 41     }
 42     void clear(int x)
 43     {
 44         for(;c[x];x+=lowbit(x))
 45         {
 46             c[x]=0;
 47         }
 48     }
 49 }XX;
 50 void CDQ(int l,int r)
 51 {
 52     if(l == r) return;
 53     int mid =(l+r)>>1;
 54     CDQ (l,mid);
 55     CDQ(mid+1,r);
 56     int t1=l;
 57     int t2=mid+1;
 58     int k=l;
 59     while(t2<=r)
 60     {
 61         while(t1<=mid&&b[t1].x<=b[t2].x)
 62         {
 63             if(b[t1].time==1)
 64             {
 65                 XX.update(b[t1].y,b[t1].x+b[t1].y);
 66              } 
 67              tt[k++]=b[t1++];
 68         }
 69         if(b[t2].time==2)
 70         {
 71             a[b[t2].id].ans=min(a[b[t2].id].ans,b[t2].x+b[t2].y-XX.sum(b[t2].y));    
 72         }
 73         tt[k++]=b[t2++];
 74     }
 75     for(int i=l;i<=t1-1;i++)
 76     {
 77         if(b[i].time==1)
 78         {
 79             XX.clear(b[i].y);
 80         }
 81     }
 82     
 83     while(t1<=mid)
 84     {
 85         tt[k++]=b[t1++];
 86     }
 87     for(int i=l;i<=r;i++)
 88     {
 89         b[i]=tt[i];
 90     }
 91 }
 92 void solve(int x1,int y1)
 93 {
 94     for(int i=1;i<=n+q;i++)
 95     {
 96         b[i]=a[i];
 97         if(x1)
 98         {
 99             b[i].x=len-b[i].x;
100         }
101         if(y1)
102         {
103             b[i].y=len-b[i].y;
104         }
105     }
106     CDQ(1,n+q);
107 }
108 int main()
109 {
110     scanf("%d%d",&n,&q);
111     for(int i=1;i<=n;i++)
112     {
113         scanf("%d%d",&x,&y);
114         a[i].time=1;
115         a[i].id=i;
116         a[i].x=++x;
117         a[i].y=++y;
118         len=max(len,max(x,y));
119     }
120     for(int i=n+1;i<=n+q;i++)
121     {
122         scanf("%d%d%d",&flag,&x,&y);
123         a[i].time=flag;
124         a[i].id=i;
125         a[i].x=++x;
126         a[i].y=++y;
127         a[i].ans=inf;
128         len=max(len,max(x,y));
129     }
130     len++;
131     solve(0,0);
132     solve(0,1);
133     solve(1,0);
134     solve(1,1);
135     for(int i=n+1;i<=n+q;i++)
136     {
137         if(a[i].time ==2)
138         {
139             printf("%d
",a[i].ans);
140         }
141     }
142     return 0;
143  }