牛客寒假算法基础集训营5 E. 炫酷划线(树状数组)

#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int pre[maxn];
int T,n,m;

int lowbit(int x){
  return x & (-x);
}

void Update(int x,int y){
  for(int i=x;i<=n;i+=lowbit(i)){
    pre[i] += y;
  }
}

int Query(int x){
  int sum = 0;
  for(int i=x;i>=1;i-=lowbit(i)){
    sum += pre[i];
  }
  return sum;
}

int main()
{
  scanf("%d",&T);
  while(T--){
    memset(pre, 0, sizeof(pre));
    bool flag = false;
    scanf("%d%d",&n,&m);
    int pos = -1;
    for(int i=1;i<=m;i++){
      int l, r;
      scanf("%d%d",&l, &r);
      if(l > r) swap(l, r);
      if(flag == false){
        int xx = Query(l - 1);
        int yy = Query(r);
        if(yy - xx != 0){
          pos = i;
          flag = true;
        }
        else{
          Update(l, i);
          Update(r, -i);
        }
      }
    }
    printf("%d\n", pos);
  }
  return 0;
}