#include<iostream>
#include<cstdio>
using namespace std;
int c1[200005];
int c2[200005];
int n,m;
int lowbit(int x)
{
return x&(-x);
}
void addx(int x,int v)
{
while(x<=n)
{
c1[x]+=v;
x+=lowbit(x);
}
}
void addy(int x,int v)
{
while(x<=n)
{
c2[x]+=v;
x+=lowbit(x);
}
}
int sumx(int x)
{
int res=0;
while(x>0)
{
res+=c1[x];
x-=lowbit(x);
}
return res;
}
int sumy(int x)
{
int res=0;
while(x>0)
{
res+=c2[x];
x-=lowbit(x);
}
return res;
}
int main()
{

cin>>n>>m;
int p,q,t;
for(int i=1;i<=m;i++)
{
cin>>t>>p>>q;
if(t==1)
{
addx(p,1);
addy(q,1);
}
if(t==2)
{
cout<<sumx(q)-sumy(p-1)<<endl;
}
}
return 0;//树状数组模板题
}

容易发现答案为\(\sum_{i} [l_i \le r]-[r_i < l]\)，树状数组记录\(\leq k\)的\(l_i\)和\(r_i\)的个数即可。

#include <bits/stdc++.h>
using namespace std;
const int MAXSIZE=30000020;
int bufpos;
char buf[MAXSIZE];
void init(){
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=(buf[bufpos]=='-'))?1:0;
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
struct bit{
    int n;
    int a[50002];
    void add(int p,int v){
        for(;p<=n;p+=p&-p)
            a[p]+=v;
    }
    int query(int p){
        int ans=0;
        for(;p;p-=p&-p)
            ans+=a[p];
        return ans;
    }
}bl,br;
int main(){
    init();
    bl.n=br.n=readint();
    int m=readint();
    while(m--){
        int k=readint(),l=readint(),r=readint();
        if (k==1)
            bl.add(r,1),br.add(l,1);
        else printf("%d\n",br.query(r)-bl.query(l-1));
    }
}

求解为啥？
c++
#include<stdio.h>
#define LB(x) (x&-x)
int a[50010],b[50010],n,m;
void add(int s[],int x){
for(;x<=n;x+=LB(x))
s[x]++;
}
int query(int s[],int x){
int ans=0;
for(;x;x-=LB(x))
ans+=s[x];
return ans;
}
int main(){
scanf("%d%d",&n,&m);
for(int t,l,r,i=0;i<m;++i){
scanf("%d%d%d",&t,&l,&r);
if(t==1){ add(b,r); add(a,l); }
else printf("%d\n",query(a,r)-query(b,l-1));
}
}


用树状数组，快且简单，不过格式错误。。。

改成不换行输出：

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：18ms

郁闷！

漂亮的树状数组....

50000的nlogn比赛40

再交70

再交80

……………………

更新：

才发现我maxn=501000…………………………

我理解错题目了么？？如果种树段有重叠是怎么算？把原来的树T掉？还是保持原来位置？还是再种新的一棵？

问大家一下：这道题到底应该怎么做啊？

有史以来通过率最低的题可能要产生了

题解：

在l处添加一个左括号，在y处添加一个右括号。

ans=1~r的左括号-1~l-1的右括号

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 25ms

├ 测试数据 07：答案正确... 712ms

├ 测试数据 08：答案正确... 1400ms

├ 测试数据 09：答案正确... 3666ms

├ 测试数据 10：答案正确... 3744ms

with tiger

PS：同志们一定要write啊！！

线段树？

终于AC了，

同一个程序不同的评测机，比赛时只有60分，。。。。。。。

看看现在的效率，就知道doplin有多么烂了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 25ms

├ 测试数据 08：答案正确... 56ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 9ms

完全一样的程序,都是Lora Temper评测机,结果竟然还能不一样

orz

弱弱的问一句。。。这题用线段树肿么解啊？

编译成功

Free Pascal Compiler version 2.6.4 [2014/03/06] for i386
Copyright (c) 1993-2014 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(12,39) Warning: Variable "l" does not seem to be initialized
foo.pas(13,39) Warning: Variable "r" does not seem to be initialized
Linking foo.exe
19 lines compiled, 0.1 sec , 28224 bytes code, 1628 bytes data
2 warning(s) issued

测试数据 #0: Accepted, time = 0 ms, mem = 1120 KiB, score = 1

测试数据 #1: Accepted, time = 0 ms, mem = 1124 KiB, score = 1

测试数据 #2: Accepted, time = 46 ms, mem = 1124 KiB, score = 1

测试数据 #3: Accepted, time = 109 ms, mem = 1124 KiB, score = 1

测试数据 #4: Accepted, time = 265 ms, mem = 1124 KiB, score = 1

测试数据 #5: Accepted, time = 250 ms, mem = 1124 KiB, score = 1

测试数据 #6: Accepted, time = 1843 ms, mem = 1128 KiB, score = 1

测试数据 #7: Accepted, time = 3390 ms, mem = 1128 KiB, score = 1

测试数据 #8: Accepted, time = 8437 ms, mem = 1124 KiB, score = 1

测试数据 #9: Accepted, time = 8546 ms, mem = 1124 KiB, score = 1

Accepted, time = 22886 ms, mem = 1128 KiB, score = 10

var
l,r:array[1..50001]of longint;
n,m,i,j,x,y,k:longint;

begin
readln(n,m);
for i:=1to m do
begin
read(k);
if k=1 then begin
readln(x,y);
for j:=1to x do inc(l[j]);
for j:=1to y do inc(r[j]);
end
else begin
readln(x,y);
writeln(r[x]-l[y+1]);
end;
end;
end.

╮(╯▽╰)╭

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

第一次做线段树就一次秒杀了^_^