树状数组暴力,但是没过样例。
查看原帖
树状数组暴力,但是没过样例。
749325
Sincerin楼主2022/11/30 13:49

RT

萌新初学数据结构,从隔壁大水题P2846过来的,感觉题目几乎完全一样啊?期望得分60,实际样例过不掉。有没有大佬看看哪里出问题了呀?感谢!

#include<stdio.h>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<time.h>
#include<bitset>
using namespace std;
int n,m,id,l,r;
int a[200005];
string s;
long long ans;
inline void add(int x,int k)
{
    for(register int i=x;i<=n;i+=i&-i) a[i]+=k;
}
inline int query(int x)
{
    int ans=0;
    for(register int i=x;i>0;i-=i&-i) ans+=a[i];
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	cin>>n>>m;
	cin>>s;
	for(register int i=1;i<=n;i++) a[i]=s[i-1]-'0';
    for(register int i=1;i<=m;i++)
	{
	   	cin>>id;
	   	if(id==0)
		{
	   		cin>>l>>r;
	   		add(l,1);
			add(r+1,1);
	   	}
	   	if(id==1)
		{   
	   		cin>>l>>r;
	   		ans=0;
	   		for(register int i=l;i<=r;i++) if(query(i)&1==1) ans++;
	   		cout<<ans<<"\n";	
	   	}
   }
   return 0;
}

不要凶凶!

2022/11/30 13:49
加载中...