UVA12356 Army buddies TLE错误！

[ghost]

#include<bits/stdc++.h>
using namespace std;
int main()
{
     ios::sync_with_stdio(false);
     int n;int m;
     while(cin>>n>>m&&n!=0&&m!=0)
     {
       int arr[n+1]; 
       for(int i=1;i<=n;i++)arr[i]=i;    //给每个士兵编号

       while(m--)
       {
         int l,r;
         cin>>l>>r;                     //控制左右被杀死士兵
         for(int i=l;i<=r;i++)arr[i]=0;//杀死这些士兵

         int cnt=0;
         for(int i=r;i>=1;i--)    //左边buddle判断
         {
           if(arr[i]!=0)
           {
             cout<<arr[i]<<" ";
             cnt++;
             break;
           }
         }
         if(cnt==0)cout<<'*'<<" ";

         cnt=0;
         for(int i=l;i<=n;i++)   //右边buddle判断
         {
           if(arr[i]!=0)
           {
             cout<<arr[i]<<endl;
             cnt++;
             break;
           }
         }
         if(cnt==0)cout<<'*'<<endl;
       }
       cout<<'-'<<endl;          //结束分割线
     }
       return 0;

}

[ghost]

这里是在什么地方造成了TLE的错误，又需要怎么去优化他

[volmodaoist]

　注意数据范围，每次修改（更新死亡士兵）复杂度都是，每对输入的都要更新一次，共有B 对，那么复杂度，根据题目给出的数据范围来看，都非常大，取其最大值可以算得数据量远大于，而我们之前已经说过数据量大于这个范围必然 TLE。

[volmodaoist]

　作为一个维护区间的题目，首先应当考虑一下能够维护区间的结构有哪些，差分数组+前缀和？这个实现比较简单，但是对于本题来说，由于修改频繁，这个结构无法起到降低复杂度的作用，而树状数组、线段树，实现起来又过于复杂，凡此种种都不太适合。那么有没有更合适的结构呢？有！双向链表！但是链表修改首先需要找到对应的结点吧？这个查找操作可就已经复杂度了，所以这时候要用数组模拟链表，利用数组随机访问(也称下标访问）这一特性以及链表快速修改的特性！

[volmodaoist]

说起来比较抽象，建议直接阅读代码！

#include "bits/stdc++.h"
#include <iomanip>
using namespace std;

int lnode[100005];
int rnode[100005];

int main(){

    int s,b,lo,hi;
    while(cin>>s>>b){
        if(s==0 && b==0)
            break;
        for(int i = 1; i <= s; i++){
            lnode[i] = i - 1;
            rnode[i] = i + 1; 
        }
        for(int i = 1; i <= b; i++){
            cin>>lo>>hi;
            lnode[rnode[hi]] = lnode[lo];
            rnode[lnode[lo]] = rnode[hi];
            if(lnode[lo] <= 0){
                cout<<"*"<<" ";
            }else{
                cout<<lnode[lo]<<" ";
            }
            if(rnode[hi] > s){
                cout<<"*"<<endl;
            }else{
                cout<<rnode[hi]<<endl;
            }
        }
        cout<<"-"<<endl;
    }
    return 0;
}

核心操作其实只有两部分，首先是利用数组模拟静态链表

  for(int i = 1; i <= s; i++){
      lnode[i] = i - 1;
      rnode[i] = i + 1; 
  }

然后便是修改区间：

lnode[rnode[hi]] = lnode[lo]; //hi结点右边的hi+1结点的左指针指向lo-1结点
rnode[lnode[lo]] = rnode[hi]; //lo结点左边的lo-1结点的右指针指向hi+1结点

　这两句代码有点难懂，建议画一下图，自行理解一番，另外本题过于经典，建议把数据模拟双向链表的操作给直接背下来当做模板使用！