践踏

C++14(g++5.4) 解法, 执行用时: 69ms, 内存消耗: 2852K, 提交时间: 2019-07-15 20:54:49

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int tr[maxn],num[2*maxn];
struct node
{
	int o,l,r,x;
}q[maxn];
int n;
void updata(int l,int r,int val)
{
	for(int i=l;i<maxn;i+=i&-i){
		tr[i]+=val;
	}
	for(int i=r+1;i<maxn;i+=i&-i){
		tr[i]-=val;
	}
}
int query(int x)
{
	int rec=0;
	while(x){
		rec+=tr[x];
		x-=x&-x;
	}
	return rec;	
}
int main()
{
	int k,o,l,r,x;
	scanf("%d%d",&n,&k);
	if(n==0){
		printf("fafa\n");
		return 0;
	}
	int cnt=0;
	if(k==0){
		for(int i=1;i<=n;i++){
			scanf("%d",&o);
			if(o==1||o==2){
				scanf("%d%d",&l,&r);
				num[++cnt]=l;
				num[++cnt]=r;
				q[i].l=l;q[i].o=o;q[i].r=r;
			}
			else{
				scanf("%d",&x);
				num[++cnt]=x;
				q[i].o=o;q[i].x=x;
			}
		}
		sort(num+1,num+cnt+1);
		cnt=unique(num+1,num+cnt+1)-num-1;
		for(int i=1;i<=n;i++)
		{
			if(q[i].o==1){
				l=lower_bound(num+1,num+cnt+1,q[i].l)-num;
				r=lower_bound(num+1,num+cnt+1,q[i].r)-num;
				updata(l,r,1);
			}
			else if(q[i].o==2){
				l=lower_bound(num+1,num+cnt+1,q[i].l)-num;
				r=lower_bound(num+1,num+cnt+1,q[i].r)-num;
				updata(l,r,-1);
			}
			else{
				x=lower_bound(num+1,num+cnt+1,q[i].x)-num;
				printf("%d\n",query(x));
			}
		}
	}
	else{
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&o);
			if(o==1){
				scanf("%d%d",&l,&r);
				if(r-l+1>=k){
					updata(1,k,1);
				}
				else{
					l=l%k+1;
					r=r%k+1;
					if(l>r){
						updata(1,r,1);
						updata(l,k,1);
					}
					else
						updata(l,r,1);
				}
			}
			else if(o==2){
				scanf("%d%d",&l,&r);
				if(r-l+1>=k)
					updata(1,k,-1);
				else{
					l=l%k+1;
					r=r%k+1;
					if(l>r){
						updata(1,r,-1);
						updata(l,k,-1);
					}
					else
						updata(l,r,-1);
				}
			}
			else{
				scanf("%d",&x);
				x=x%k+1; 
				printf("%d\n",query(x));
			}
		}
	}
}

C++(g++ 7.5.0) 解法, 执行用时: 149ms, 内存消耗: 2084K, 提交时间: 2022-11-29 19:16:57

#include<bits/stdc++.h>
using namespace std;
struct FenWick {
  int lowbit(int x) {return x&-x;}
  vector<int> S;
  int N;
  FenWick(int N) { init(N); }
  void init(int N) {
    this->N = N;
    S.clear(); S.resize(N+1);
  }
  void add(int i, int x) {
    while (i <= N) S[i] += x, i += lowbit(i);
  }
  int64_t sum(int i) {
    int64_t tot = 0;
    while (i) tot += S[i], i -= lowbit(i);
    return tot;
  }
};


int main(){
  int n, k; cin >> n >> k;
  if (n == 0) {
    cout << "fafa" << endl;
    return 0;
  }
  FenWick F(k?k+1:123456);
  while (n--) {
    int op; cin >> op;
    if (op == 3) {
      int x; cin >> x; 
      if(k) x %= k;
      if (x > F.N) cout << 0 << endl;
      else  cout << F.sum(x+1)  << endl;
    } else {
      int inc = op == 1?1: -1;
      int l, r; cin >> l >> r;
      r++;
      if (k&&r - l >= k) {
        F.add(1, inc);
      } else {
        if (k) l%=k, r%=k;
        l++, r++;
        if (l < r) {
          F.add(l, inc);
          F.add(r, -inc);
        } else {
          F.add(1, inc);
          F.add(r, -inc);
          F.add(l, inc);
        }
      }
    }
  }
  
}

C++11(clang++ 3.9) 解法, 执行用时: 77ms, 内存消耗: 2524K, 提交时间: 2019-09-30 16:35:51

#include<bits/stdc++.h>
using namespace std;
#define M 100005
#define N 200005
int n,k,op,i,l,r,ans,res,c[N],b[N],si;
struct node {
	int op,l,r;
} a[M];
int sum(int x) {
	x++;
	int res=0;
	while(x)res+=c[x],x-=x&-x;
	return res;
}
void add(int x,int d) {
	x++;
	while(x<N)c[x]+=d,x+=x&-x;
}
int find(int x) {
	return lower_bound(b+1,b+si+1,x)-b;
}
int main() {
	scanf("%d%d",&n,&k);
	if(!n)printf("fafa\n");
	else if(!k) {
		for(i=1; i<=n; i++) {
			scanf("%d%d",&a[i].op,&a[i].l),b[++si]=a[i].l;
			if(a[i].op<3)scanf("%d",&a[i].r),b[++si]=a[i].r;
		}
		sort(b+1,b+si+1),si=unique(b+1,b+si+1)-b-1;
		for(i=1; i<=n; i++)
			if(a[i].op==3)printf("%d\n",sum(find(a[i].l)));
			else op=a[i].op==1?1:-1,add(find(a[i].l),op),add(find(a[i].r)+1,-op);
	} else {
		for(i=1; i<=n; i++) {
			scanf("%d%d",&op,&l);
			if(op==3)printf("%d\n",res+sum(l%k));
			else {
				if(op==2)op=-1;
				scanf("%d",&r);
				if(r-l+1>=k)res+=op;
				else {
					r%=k,l%=k;
					if(l<=r)add(l,op),add(r+1,-op);
					else add(l,op),add(r+1,-op),add(0,op);
				}
			}
		}
	}
	return 0;
}

详情