Vijos 1448 校门外的树 树状数组

描述

校门外有很多树,有苹果树,香蕉树,有会扔石头的,有可以吃掉补充体力的……
如今学校决定在某个时刻在某一段种上一种树,保证任一时刻不会出现两段相同种类的树,现有两个操作:
K=1,K=1,读入l、r表示在区间[l,r]中种上一种树,每次操作种的树的种类都不同
K=2,读入l,r表示询问l~r之间能见到多少种树
(l,r>0)
格式

输入格式

第一行n,m表示道路总长为n,共有m个操作
接下来m行为m个操作
输出格式

对于每个k=2输出一个答案
样例1

样例输入1

5 4
1 1 3
2 2 5
1 2 4
2 3 5
Copy
样例输出1

1
2
Copy
限制

1s
提示

范围:20%的数据保证,n,m<=100
60%的数据保证,n <=1000,m<=50000
100%的数据保证,n,m<=50000
来源

dejiyu@CSC WorkGroup

相当与给你一大堆线段,问给你的区间与多少线段有交点
于是有了一种十分魔性的方法:括号法
假设有一个长度为10的数轴,我们要将区间[ 2 , 5 ]中种树,这时,我们将 2 处放一个左括号 ” ( ” ,5处放一个 ” )” ,表示区间 [ 2 , 5 ]种了树。
查询某个区间树的种类,如区间[ 3 , 10],只需统计10之前(包括10)有多少个‘(’,统计3之前有多少个‘)’,(不包括3)。
然后维护一个树状数组就ok了

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#define N 100005
using namespace std;
int n,m;
int h[N];
int t[N];
inline int lowbit(int x){
  return x&(-x);}
inline void add(int a[],int k){
    for(int i=k;i<=n;i+=lowbit(i)) a[i]++;
}
inline int sum(int a[],int k){
    int ans=0;
    for(int i=k;i>0;i-=lowbit(i)) ans+=a[i];
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int k,x,y;
        scanf("%d%d%d",&k,&x,&y);
        if(k==1){
            add(h,x);
            add(t,y);
        }
        else{
            printf("%d\n",sum(h,y)-sum(t,x-1));
        }
    }

    return 0;
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
2022-12-02 12:05
重庆大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议