P2184 贪婪大陆题解

iloveori 2021-08-27 原文

P2184 贪婪大陆题解

P2184 贪婪大陆

题目描述

小FF最后一道防线是一条长度为N的战壕，小FF拥有无数多种地雷，而SCV每次可以在$[ L , R ]$区间埋放同一种不同于之前已经埋放的地雷。由于情况已经十万火急，小FF在某些时候可能会询问你在$[ L\’ , R\’] $区间内有多少种不同的地雷，他希望你能尽快的给予答复。

对于30%的数据： $0<=n, m<=1000$;

对于100%的数据： $0<=n, m<=10^5$.

输入格式

第一行为两个整数$n$和$m$；

$n$表示防线长度，$m$表示SCV布雷次数及小FF询问的次数总和。

接下来有$m$行，每行三个整数$Q,L,R$；若$Q=1$ 则表示SCV在$[L,R]$这段区间布上一种地雷，若$Q=2$则表示小FF询问当前$[ L , R ]$区间总共有多少种地雷。

输出格式

对于小FF的每次询问，输出一个答案（单独一行），表示当前区间地雷总数。

输入输出样例

输入

输出

1
2

题解

分析

我们查的时候，我们只需要查1到当前区间结尾中包含了多少个开头，然后我们查1到当前区间前一个位置包含了多少个结尾，然后把这个做差，我们就可以知道有多少种地雷是出现在当前区间中，然后这道题就成功的被我们转化成了一个单点修改，区间查询的简单的问题。

用线段树和树状数组都可，看个人喜好，下面是比较简单的树状数组代码$\downarrow$

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;

template <typename T>
inline void read(T &x) {
	x = 0;
	ll f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == \'-\') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch ^ 48);
        ch = getchar();
    }
    x *= f;
    return;
}
template <typename T>
inline void write(T x){
    if(x < 0) {
        putchar(\'-\');
        x = -x;
    }
    if(x > 9)
        write(x/10);
    putchar(x % 10 + \'0\');
    return;
}
int head[500005], tail[500005], n, m;
inline int lowbit(int x){return x & (-x);}
inline void add_head(int x){
    for (int i = x; i <= n; i += lowbit(i))
        head[i]++;
}
inline void add_tail(int x){
    for (int i = x; i <= n; i += lowbit(i))
        tail[i]++;
}
inline int sum_head(int x){
    int s = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        s += head[i];
    return s;
}
inline int sum_tail(int x)
{
    int s = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        s += tail[i];
    return s;
}
int main(){
    int qwq,x,y;
    read(n), read(m);
    for (register int i = 1; i <= m; i++)
    {
        read(qwq);
        read(x);
        read(y);
        if(qwq==1)
        {
            add_head(x),add_tail(y);
        }
        else
            cout << sum_head(y) - sum_tail(x-1) << endl;
        
    }
        return 0;
}