[HOJ 282] Empire disruption

作法：

首先注意到，對於每個計劃的相鄰兩個給定的城市，只要$x+y$的值比兩個城市之間的距離左右還大，那麼這兩個城市佔領的區域就會重疊。並且當兩相鄰城市佔領的區域重疊時，他們所佔領的總城市數就會是這兩個城市之間的城市數（含端點）加上$x+y$（不考慮左右邊界的話）。因此我們可以按照詢問的$x+y$值從小到大排序，每次如果發現有相鄰城市佔領的區域重疊了，就把他們黏起來。於是現在會變成有很多被黏起來的相鄰的城市們，我們需要知道總共有幾陀，還有這些城市區間內部的城市數量是多少。而這只要對於每一陀被黏起來的的城市，假設他最左和最右的城市分別是$X$和$Y$好了，那麼就用兩個陣列$le,ri$紀錄好$ri[X]=Y$，還有$le[Y]=X$就可以了。實作上我是將所有的兩個相鄰的給定城市之間的距離 sort ，還有詢問當然按照$x+y$值sort，並且當遇到一個詢問時把所有該黏起來的城市黏起來就可以了。最後要記得考慮超出邊界的問題，這只要用$a[1],a[n]$和當次詢問的$x,y$值就可以判斷了。

code :

#include<bits/stdc++.h>
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
const int maxn=100000+10 ;
 
struct qu
{
    int x,y,id ;
    bool operator < (const qu &rhs) const
    {
        return x+y<rhs.x+rhs.y ;
    }
}q[maxn];
int ans[maxn] ;
int le[maxn],ri[maxn] ;
int a[maxn] ;
pii p[maxn] ;
main()
{
    int m,n,Q ; scanf("%d%d%d",&m,&n,&Q) ;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]) ;
        le[i]=ri[i]=i ;
        if(i>1) p[i-1]=(pii){a[i]-a[i-1],i-1} ;
    }
    for(int i=1;i<=Q;i++) scanf("%d%d",&q[i].x,&q[i].y) , q[i].id=i ;
    sort(p+1,p+n) ; sort(q+1,q+Q+1) ;
 
    int num=n,tot=n ;
    for(int i=1,j=1;i<=Q;i++)
    {
        for(;j<n && p[j].F<=q[i].x+q[i].y+1;j++)
        {
            int x=p[j].S ;
            tot-=a[x]-a[le[x]]+1+a[ri[x+1]]-a[x+1]+1 ;
            tot+=a[ri[x+1]]-a[le[x]]+1 ;
            num-- ;
            le[ri[x+1]]=le[x] ;
            ri[le[x]]=ri[x+1] ;
        }
        ans[q[i].id]=tot+num*(q[i].x+q[i].y) ;
        if(q[i].x>=a[1]) ans[q[i].id]-=q[i].x-a[1]+1 ;
        if(a[n]+q[i].y-1>=m) ans[q[i].id]-=(a[n]+q[i].y-m) ;
    }
    for(int i=1;i<=Q;i++) printf("%d\n",ans[i]) ;
}