显然可以直接贪心，即每一次移动尽量少的距离，时间复杂度为$o(nm)$
不难发现，以下两类攻击可以被删除：
1.连续两次攻击位置相同，则删除其中一次攻击
2.连续三次攻击位置形如$ab>c$，则删除中间的攻击
此时，攻击位置即形如$a_{1}a_{3}...$（或交换$<$和$>$）
取其中最近的两次攻击，假设为$a_{x}$和$a_{x+1}$，对防壁长度$len$分类讨论：
1.若$len<|a_{x}-a_{x+1}|$，此时答案即$\sum_{i=1}^{m-1}|a_{i}-a_{i+1}|$（需要特殊处理前两次攻击）
2.若$len\ge |a_{x}-a_{x+1}|$，此时以下两类攻击可以被删除——
(1)若$x\ge 2$，则删除$a_{x}$，具体原因如下：
不妨假设$a_{x}a_{x+1}$，进而在操作$a_{x}$后一定已覆盖$a_{x+1}$
(2)若$x+1
当$m\ge 3$时显然每一轮至少删除一个，并需要在删除处重新处理开头的两种删除
具体可以用链表+set（找最小）实现，另外当$m\le 2$直接暴力即可
时间复杂度为$o(n+m\log m)$，可以通过
1 #include
2 using namespace std;
3 #define N 200005
4 #define ll long long
5 int n,m,n0,m0,x,L[N],R[N],id[N],a[N],pre[N],nex[N];
6 ll sum,ans[N];
7 setint,int> >S;
8 int get_len(int k){
9 return R[k]-L[k];
10 }
11 int get_val(int k){
12 return abs(a[k]-a[nex[k]]);
13 }
14 bool cmp(int x,int y){
15 return get_len(x)<get_len(y);
16 }
17 void add_S(int k){
18 sum+=get_val(k),S.insert(make_pair(get_val(k),k));
19 }
20 void del_S(int k){
21 sum-=get_val(k),S.erase(make_pair(get_val(k),k));
22 }
23 void del(int k){
24 m0--;
25 if (pre[k])del_S(pre[k]);
26 if (nex[k])del_S(k);
27 nex[pre[k]]=nex[k],pre[nex[k]]=pre[k];
28 if ((pre[k])&&(nex[k]))add_S(pre[k]);
29 }
30 void move(int k,int x){
31 if (xx;
32 if (R[k]x;
33 }
34 int main(){
35 scanf("%d%d",&n,&m);
36 for(int i=1;i<=n;i++){
37 scanf("%d%d",&L[i],&R[i]);
38 id[i]=i;
39 }
40 sort(id+1,id+n+1,cmp);
41 for(int i=1;i<=m;i++){
42 scanf("%d",&x);
43 if ((m0)&&(a[m0]==x))continue;
44 while ((m0>1)&&((a[m0-1];
45 a[++m0]=x;
46 }
47 n0=1,pre[0]=m0;
48 for(int i=0;i1,pre[i+1]=i;
49 for(int i=1;i)add_S(i);
50 while (m0>2){
51 int k=(*S.begin()).second;
52 while ((n0<=n)&&(get_len(id[n0])<get_val(k))){
53 ans[id[n0]]=sum-get_val(nex[0])-(ll)(m0-2)*get_len(id[n0]);
54 move(id[n0],a[nex[0]]),move(id[n0],a[nex[nex[0]]]);
55 n0++;
56 }
57 if (pre[k])del(nex[k]);
58 if (nex[k])del(k),k=pre[k];
59 while (1){
60 int nk=nex[k];
61 if ((!k)||(!nk))break;
62 if (a[k]==a[nk]){del(nk);continue;}
63 if ((pre[k])&&((a[pre[k]]continue;}
64 if ((nex[nk])&&((a[k]continue;}
65 break;
66 }
67 }
68 for(int i=n0;i<=n;i++){
69 move(id[i],a[nex[0]]);
70 if (m0>1)move(id[i],a[nex[nex[0]]]);
71 }
72 for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
73 return 0;
74 }