1032 换个角度思考 树状数组 离线算法 区间有多少小于等于k的数

标签：10 树状 int 离线 cin 区间 while 数组 1032

 链接：https://ac.nowcoder.com/acm/contest/26896/1032
来源：牛客网

题目描述

给定一个序列，有多次询问，每次查询区间里小于等于某个数的元素的个数
即对于询问 (l,r,x)，你需要输出 ∑i=lr[ai≤x]\sum_{i=l}^{r}[a_i \le x]∑i=lr​[ai​≤x] 的值
其中 [exp] 是一个函数，它返回 1 当且仅当 exp 成立，其中 exp 表示某个表达式

输入描述:

第一行两个整数n,m
第二行n个整数表示序列a的元素，序列下标从1开始标号，保证1 ≤ a

_i

 ≤ 10

⁵

之后有m行，每行三个整数(l,r,k)，保证1 ≤ l ≤ r ≤ n，且1 ≤ k ≤ 10

⁵

输出描述:

对于每一个询问，输出一个整数表示答案后回车

示例1

输入

复制 5 1 1 2 3 4 5 1 5 3

5 1
1 2 3 4 5
1 5 3

输出

复制 3

3

备注:

数据范围
1 ≤ n ≤ 10

⁵

1 ≤ m ≤ 10

⁵

分析

换个角度思考，这个名字起的很妙。

一开始暴力的想法：按照询问的区间，将这个区间的值挨个放入树状数组。

然后想着，给查询的区间按照右节点排序，从左往右遍历数组，并挨个插入，同时定位区间右节点，求解l 到 r 区间内小于等于k 的数的答案，但这个思路明显也行不通（l的位置没定下来，之前的值也已经插入树状数组中了）

直到。。

给数组本身按照值从小到大排序，同时给查询区间也按照值从小到大排序，当前遍历了多大的数组值，就遍历多大限制的区间范围，并求解区间内有多少个数即可算出答案。太妙了

//-------------------------代码----------------------------

#define int ll
const int N = 1e5+10;
int n,m;
struct node1 {
    int v,id;
    bool operator<(const node1 & W) const {
        return v<W.v;
    }
}a[N];
struct node2 {
    int l,r,k,id;
    bool operator<(const node2 & W) const {
        return k < W.k;
    }
}p[N];
int tr[N],ans[N];

void add(int x,int c) {
    for(int i = x;i< N;i+=lowbit(i)) tr[i]+=c;
}
int sum(int x) {int res = 0;for(int i = x;i;i-=lowbit(i))res += tr[i];
    return res;
}

void solve()
{
    cin>>n>>m;
    fo(i,1,n) cin>>a[i].v,a[i].id = i;
    sort(a+1,a+1+n);
    fo(i,1,m) {
        cin>>p[i].l>>p[i].r>>p[i].k;p[i].id = i;
    }
    sort(p+1,p+1+m);int j = 1;
    fo(i,1,n) {
        while(p[j].k < a[i].v && j <= m)ans[p[j].id] = sum(p[j].r) - sum(p[j].l-1),j++;
        add(a[i].id,1);
    }
    while(j<=m)ans[p[j].id] = sum(p[j].r) - sum(p[j].l-1),j++;
    for(int i = 1;i<=m;i++) cout<<ans[i]<<endl;
    rt;
}
void main_init() {}
signed main(){
    AC();clapping();TLE;
    cout<<fixed<<setprecision(12);
    main_init();
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
//    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------

 

标签：10,树状,int,离线,cin,区间,while,数组,1032
From： https://www.cnblogs.com/er007/p/16581829.html