Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

牛客国庆训练 H.千万别用树套树

Zzqf 2019-11-04 11:55:00 阅读数:66 评论数:0 点赞数:0 收藏数:0

链接https://ac.nowcoder.com/acm/contest/1108/H

国庆队内训练的题,当时还完全没思路,就没补。现在会树状数组了,倒是能想一想,不过网上题解好多用线段树传数组的?我看不太懂,觉得还是树状数组维护方便多了。

建两颗BIT维护分别维护左右端点。

由于对于第二种询问操作,ri-li<=2,带来了极大的便利。直接用已插入的总数-左端点大于l的线段个数-右端点小于r的线段个数即可,但有种情况需要特判。

而我网上看的题解,大部分都忽略了一个问题,就是线段退化成点的问题,样例里也给出了这样的情况,显然对于操作2,ri-li==2时,这样退化的线段会被减去两次,但令人惊讶的是数据出水了,导致不考虑这个问题也能AC。。。。。。

 

比如说 

3 3

1 2 2

1 2 2

2 1 3

这组数据网上大部分的题解的代码会输出-2,中间这个点被减了两遍。

应对也很简单,再用一个数组在插入时,保存l==r的单独的点即可,询问时在加上。

 #include <bits/stdc++.h>
#define debug(x) cout << #x << ": " << x << endl
using namespace std;
 typedef long long ll;
 const int MAXN=1e5+;
 const int INF=0x3f3f3f3f;
 const int MOD=1e9+;

int sol[MAXN];

struct BIT
 {
 int c[MAXN];
 int lowbit(int x){return x&(-x);}
 void add(int i,int x)
  {
 while(i<MAXN)
  {
 c[i]+=x;
 i+=lowbit(i);
  }
  }
 ll sum(int i)
  {
 ll res=;
 while(i)
  {
 res+=c[i];
 i-=lowbit(i);
  }
 return res;
  }
 }L,R;

int main()
 {
 int n,q;
 while(~scanf("%d%d",&n,&q))
  {
 memset(L.c,,sizeof(L.c));
 memset(R.c,,sizeof(R.c));
 memset(sol,,sizeof(sol));
 int cnt=;
 int ans=;
 while(q--)
  {
 int op,l,r;
 scanf("%d%d%d",&op,&l,&r);
 if(op==)
  {
 if(l==r) sol[l]++;
 L.add(l,);
 R.add(r,);
 cnt++;
  }
 else
 {
 int t1=cnt-L.sum(l);
 int t2=R.sum(r-);
 ans=cnt-t1-t2;
 if(r-l==) ans+=sol[l+];
 printf("%d\n",ans);
  }
  }
  }
 return ;
 }
View Code

 

版权声明
本文为[Zzqf]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/Zzqf/p/11791333.html