如何从矢量或集合中更有效地清除元素？

Question

问题陈述：

输入：

前两个输入整数n和m。 n是在比赛中战斗的骑士的数量（2 < = n < = 100000,1 < = m < = n-1）。 m是将要发生的战斗次数。

下一行包含n个功率级别。

接下来的m行包含两个整数l和r，表示骑士在第i场战斗中的位置范围。

每场战斗之后，除了最高等级之外的所有夜晚都将被淘汰。

每场战斗的范围是根据骑士的新位置而非原始位置给出的。

输出：

输出m条线，将含有从战斗骑士的原来的位置（索引）的第i行。每一行都是按升序排列。

样品输入：

8 4 
1 0 5 6 2 3 7 4 
1 3 
2 4 
1 3 
0 1 

样本输出：

1 2 
4 5 
3 7 
0 

下面是该过程的可视化。

  1  2 
[(1,0),(0,1),(5,2),(6,3),(2,4),(3,5),(7,6),(4,7)] 
     ----------------- 
       4  5 
[(1,0),(6,3),(2,4),(3,5),(7,6),(4,7)] 
      ----------------- 
      3   7 
[(1,0),(6,3),(7,6),(4,7)] 
     ----------------- 
    0 
[(1,0),(7,6)] 
----------- 

[(7,6)] 

我已经解决了这个问题。我的程序产生正确的输出，但是，它是O（n * m）= O（n^2）。我相信如果我从矢量中更有效地清除骑士，效率可以提高。使用集合擦除元素会更有效率吗？即擦除连续的部分，而不是单个骑士。有没有其他方法可以做到更高效？

#define INPUT1(x) scanf("%d", &x) 
#define INPUT2(x, y) scanf("%d%d", &x, &y) 
#define OUTPUT1(x) printf("%d\n", x); 

int main(int argc, char const *argv[]) { 
    int n, m; 
    INPUT2(n, m); 
    vector< pair<int,int> > knights(n); 
    for (int i = 0; i < n; i++) { 
     int power; 
     INPUT(power); 
     knights[i] = make_pair(power, i); 
    } 
    while(m--) { 
     int l, r; 
     INPUT2(l, r); 
     int max_in_range = knights[l].first; 
     for (int i = l+1; i <= r; i++) if (knights[i].first > max_in_range) { 
      max_in_range = knights[i].first; 
     } 
     int offset = l; 
     int range = r-l+1; 
     while (range--) { 
      if (knights[offset].first != max_in_range) { 
       OUTPUT1(knights[offset].second)); 
       knights.erase(knights.begin()+offset); 
      } 
      else offset++; 
     } 
     printf("\n"); 
    } 
} 

Answer 1

那么，从矢量中移除将无法确保效率。从集合或无序集合中移除会更有效（使用迭代器而不是索引）。

然而，问题仍然存在O（n^2），，因为你有两个嵌套的时间运行n * m次。

- 编辑 -

我相信我现在明白了问题:) 首先，让我们来计算上面的代码的复杂性。最糟糕的情况是所有战斗中的最大射程为1（每场战斗为2晚），而且战斗的位置并不相同。这意味着你必须米战斗（在这种情况下米= N-1〜= O（n）的）

• 第一while循环运行Ñ倍
• 对于一次，这使得每次为奔跑它n * 1 = n总计
• 第二个while循环每次运行一次，使其再次运行n。
  • 从向量删除装置n-1个转变，使得它为O（n）。

与载体总复杂的复杂性因此是为O（n^2）

首先，你并不真正需要的内部for循环。以第一骑士作为范围内的最大值，逐个比较剩余的范围并移除被击败的骑士。

现在，我相信它可以通过使用std :: map在O（nlogn）中完成。地图的关键是位置，价值是骑士的水平。

在继续进行之前，查找和在地图移除元素是对数的，迭代是不变的。

最后，你的代码应该是这样的：

while(m--) // n times 
    strongest = map.find(first_position); // find is log(n) --> n*log(n) 

    for (opponent = next of strongest; // this will run 1 times, since every range is 1 
     opponent in range; 
     opponent = next opponent) // iterating is constant 
     // removing from map is log(n) --> n * 1 * log(n) 
     if strongest < opponent 
      remove strongest, opponent is the new strongest 
     else 
      remove opponent, (be careful to remove it after iterating to next) 

好了，现在的上限将是O（2 * nlogn）= O（nlogn）。如果范围增加，则会使上回路的运行时间减少，但会增加删除操作的数量。我敢肯定的上限将不会改变，让我们成为一个功课，为您计算:)

Answer 2

与树堆一个解决方案是非常简单的。

对于每个查询，您需要通过隐式密钥拆分treap以获取对应于[l, r]范围（需要O(log n)时间）的子树。 之后，您可以遍历子树并找到最大强度的骑士。之后，您只需要将trip的[0, l)和[r + 1, end)部分与对应该骑士的节点合并即可。

很显然，除了树遍历和印刷工作的每个查询O(log n)时间解决方案的各个部分。但是，每个操作只会重新插入一个骑士，并从范围中删除剩余的骑士，所以输出的大小（以及子树的大小总和）在n中是线性的。所以总的时间复杂度是O(n log n)。

我不认为你可以用标准STL容器解决，因为there'no标准的容器，支持快速得到通过索引的迭代和删除任意元素。