#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

namespace dts
{
    struct st_node
    {
        int l,r,mid,suml,sumr;
    };
    
    int n,m;
    st_node st[(1<<18)+2];
    #define lc(now) ((now)<<1)
    #define rc(now) (((now)<<1)|1)
    
    void st_build(int now,int l,int r)
    {
        st[now].l=l,st[now].r=r;
        st[now].suml=st[now].sumr=0;
        if (l<r)
        {
            st[now].mid=(l+r)>>1;
            st_build(lc(now),l,st[now].mid);
            st_build(rc(now),st[now].mid+1,r);
        }
    }
    
    void st_update(int now,int pos,int task)//l:task=1 r:task=-1
    {
        if (st[now].l==pos&&pos==st[now].r)
        {
            if (task==1)
                st[now].suml++;
            else if (task==-1)
                st[now].sumr--;
        }
        else
        {
            if (pos<=st[now].mid)
                st_update(lc(now),pos,task);
            else if (st[now].mid+1<=pos)
                st_update(rc(now),pos,task);
            if (task==1)
                st[now].suml=st[lc(now)].suml+st[rc(now)].suml;
            else if (task==-1)
                st[now].sumr=st[lc(now)].sumr+st[rc(now)].sumr;
        }
    }
    
    int st_ask(int now,int l,int r,int task)//l:task=1 r:task=-1
    {
        if (st[now].l==l&&r==st[now].r)
        {
            if (task==1)
                return st[now].suml;
            else if (task==-1)
                return st[now].sumr;
        }
        else
        {
            if (r<=st[now].mid)
                return st_ask(lc(now),l,r,task);
            else if (st[now].mid+1<=l)
                return st_ask(rc(now),l,r,task);
            else
                return st_ask(lc(now),l,st[now].mid,task)+st_ask(rc(now),st[now].mid+1,r,task);
        }
    }
    
    void main()
    {
        scanf("%d%d",&n,&m);
        st_build(1,1,n);
        for (int i=1;i<=m;i++)
        {
            int K,l,r;
            scanf("%d%d%d",&K,&l,&r);
            if (K==1)
            {
                st_update(1,l,1);
                if (r+1<=n)
                    st_update(1,r+1,-1);
            }
            else if (K==2)
            {
                int suml=st_ask(1,1,r,1),sumr=st_ask(1,1,l,-1);
                printf("%d\n",suml+sumr);
            }
        }
    }
}

int main()
{
    dts::main();
}

简单的模板题
开两个树状数组维护即可

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=500040;
int a[maxn],b[maxn];
int n,m;
int lowbit(int x)
{
    return x&(-x);
}
void add1(int x,int y)
{
    while(x<=n)
    {
        a[x]+=y;
        x+=lowbit(x);
    }
}
void add2(int x,int y)
{
    while(x<=n)
    {
        b[x]+=y;
        x+=lowbit(x);
    }
}

int sum1(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=a[x];
        x-=lowbit(x);
    }
    return ans;
}
int sum2(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=b[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){
    cin>>n>>m;
    while(m--)
    {
        int wzx,x,y;
        scanf("%d",&wzx);
        if(wzx==1)
        {
            scanf("%d %d",&x,&y);
            add1(x,1);
            add2(y,1);
        }
        if(wzx==2)
        {
            scanf("%d%d",&x,&y);
            printf("%d\n",sum1(y)-sum2(x-1));
        }
    }
    return 0;
}

#include<stdio.h>

int main()

{

int L, M, i, j, n;

int a[10001], b[10001];

scanf("%d %d",&L, &M); //输入L和M

n = M*2;//循环输入b数组0~n的数据

for(i=0; i<n; i+=2)

{

scanf("%d %d", &b[i], &b[i+1]);

}

for(i=0; i<=L; i++) //循环给a数组L个元素赋值

{

a[i] = i;

}

int r, s;

for(i=0; i<n; i+=2) //遍历访问数组b的各个区间

{

r = b[i]; //区间起始点

s = b[i+1]; //区间终点

for(j=r; j<=s; j++) //把数组b各个区间内元素在数组a中映射为0

{

a[j] = -1;

}

}

int k=0; 

for(i=0; i<=L; i++)

{

if(a[i] != -1)

{

k++; 

}

}

printf("%d", k);

return 0;

}

#include<bits/stdc++.h>
using namespace std;int n,m,k,l,r;int a1[50005],a2[50005];int c(int x){return x&-x;}void update1(int x,int v){while(x<=n){a1[x]+=v;x+=c(x);}}void update2(int x,int v){while(x<=n){a2[x]+=v;x+=c(x);}}int sum1(int x){int res=0;while(x>0){res+=a1[x];x-=c(x);}return res;}int sum2(int x){int res=0;while(x>0){res+=a2[x];x-=c(x);}return res;}int main(){cin>>n>>m;for(int i=1;i<=m;i++){cin>>k>>l>>r;if(k==1)update1(l,1),update2(r,1);else cout<<sum1(r)-sum2(l-1)<<endl;}}
自己看吧

参考https://www.cnblogs.com/shadowland/p/5870395.html
这篇写的很好
用树状数组和线段树都可以，只要可以维护区间加法查询就可以了 - 原理是用两个数据结构分别维护每个树种区间的左端点和右端点，
设查询的区间为tl, tr
一个查询区间里存在的树种的个数（多少个不同的树种区间在我们的区间里）= [1, tr]上左端点的个数 - [1, tl - 1]上右端点的个数。这样就是所有[1, tr]上的区间里有所覆盖的树区间，去掉 只出现在[1, tl - 1]上的树区间，剩下的区间就是所有涉及到[tl, tr]的树区间辣！压力马斯内！（赞赏）

经验教训
1. 又没有好好读题，只有单个更新和区间查询，和懒更新毛线的关系都没有，不要多写。。。
2. 刚开始Runtime Error,后来一想线段树至少要开数据规模x4吧，居然没写。。。
3. 快读写了居然用了cin??? 哈 哈。对比一下快了20多ms，快读还是狠滴

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n, m;

int read() {
    int f = 1, x = 0;
    char c; c = getchar();
    if (c == '-') { f = -1; c = getchar(); }
    while ('0' <= c && c <= '9') {
        x *= 10;
        x += c - '0';
        c = getchar();
    }
    return x * f;
}

struct Node {
    int l, r, val;
    Node& operator++() { 
        val++; 
        return *this;
    }
};

const int MAXN = (5e4 + 500) * 10;

struct SegmentTree {
    int cnt, root;
    Node nodes[MAXN];

    SegmentTree() {
        getNode(root);
    }

    int getNode(int& x) {
        if (!x) { return (x = ++cnt); }
        return x;
    }

    bool exist(int x) {
        if (!x) return false;
        return true;
    }

    void add(int p, int t, int l, int r) {
        Node& curr = nodes[p];
        if (r < t || t < l || r < l) { return; }
        if (l == r && l == t) { ++curr; return; }
        else {
            int mid = (l + r) / 2;
            if (t <= mid) { add(getNode(curr.l), t, l, mid); }
            else if (t > mid) { add(getNode(curr.r), t, mid + 1, r); }
        }
        curr.val = nodes[curr.l].val + nodes[curr.r].val;
    }

    int query(int p, int tl, int tr, int l, int r) {
        Node& curr = nodes[p];
        if (tl <= l && r <= tr) return curr.val;
        if (r < tl || tr < l || !exist(p) || r < l) return 0;
        else {
            int mid = (l + r) / 2, sum = 0;
            if (tl <= mid) { sum += query(curr.l, tl, tr, l, mid); }
            if (tr > mid) { sum += query(curr.r, tl, tr, mid + 1, r); }
            return sum;
        }
    }

} lb, rb; //left bracket, right bracket

int main() {
    n = read(); m = read();
    for (int i = 1; i <= m; i++) {
        int c, param1, param2;
        c = read(); param1 = read(); param2 = read();
        if (c == 1) {
                lb.add(lb.root, param1, 1, n);
                rb.add(rb.root, param2, 1, n);
        } else {
            cout << lb.query(lb.root, 1, param2, 1, n) - rb.query(rb.root, 1, param1 - 1, 1, n) << endl;
        }
    }
    return 0;
}

树状数组解

#include <iostream>
#include <cstdio>
#define ll long long
#define rll register long long
using namespace std;
const int MAXN=5e4+5;
ll n,m,c1[MAXN],c2[MAXN];
inline ll lowbit(rll i){return i&(-i);}
inline void update1(rll x,rll value)
{
    for(rll i=x;i<=n;i+=lowbit(i))
        c1[i]+=value;
}
inline ll find1(rll x)
{
    rll res=0;
    for(rll i=x;i;i-=lowbit(i))
        res+=c1[i];
    return res;
}
inline void update2(rll x,rll value)
{
    for(rll i=x;i<=n;i+=lowbit(i))
        c2[i]+=value;
}
inline ll find2(rll x)
{
    rll res=0;
    for(rll i=x;i;i-=lowbit(i))
        res+=c2[i];
    return res;
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(rll i=1,k,l,r;i<=m;i++)
    {
        scanf("%lld%lld%lld",&k,&l,&r);
        if(k==1)
        {
            update1(l,1);
            update2(r,1);
        }
        else
            printf("%lld\n",find1(r)-find2(l-1));
    }
    return 0；
}

左右括号法
线段树||树状数组......
不存在的
#include<bits/stdc++.h>
#define F(i,j) for(int i=1;i<=j;i++)
using namespace std;
int n,m,l[50001]={0},r[50001]={0},k,x,y;;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&k,&x,&y);
if(k==1)l[min(x,y)]++,r[max(x,y)]++;
else{
int ans=0,lh=0,rh=0;
F(j,x-1)lh+=r[j];
F(j,y)rh+=l[j];
ans=rh-lh;
printf("%d\n",ans);
}
}
}

JRX2015U43：树状数组。
http://blog.csdn.net/qq_31640513/article/details/61435432

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

const int N = 50000 + 5;

int n, m, L[N], R[N];

int main() {
scanf("%d%d", &n, &m);
while (m--) {
int k, l, r;
scanf("%d%d%d", &k, &l, &r);
if (k == 1) {
for (int x = r; x <= n; x += x & -x) R[x]++;
for (int x = l; x <= n; x += x & -x) L[x]++;
} else {
int ans = 0;
for (int x = r; x; x -= x & -x) ans += L[x];
for (int x = l - 1; x; x -= x & -x) ans -= R[x];
printf("%d\n", ans);
}
}
return 0;
}

#include <bits/stdc++.h>
#define maxN 200010 

using namespace std ;
typedef long long QAQ ;

struct Tree{int l , r ; QAQ liml , limr ;};

Tree tr[maxN<<2];

void Build_Tree ( int x , int y , int i ){
    tr[i].l = x ;
    tr[i].r = y ;
    if( x==y )return ;
    else {
        QAQ mid = (tr[i].l + tr[i].r) >> 1 ;
        Build_Tree ( x , mid , i<<1);
        Build_Tree ( mid+1 , y , i<<1|1);
        return ;
    }
}

void Update_left ( int w , int i ){
    if( w==tr[i].l && w==tr[i].r )tr[i].liml++;
    else {
        QAQ mid = (tr[i].l + tr[i].r) >> 1 ;
        if( w>mid )Update_left( w , i<<1|1);else
        if( w<=mid)Update_left( w , i<<1 );
        tr[i].liml = tr[i<<1].liml + tr[i<<1|1].liml ;
    }
}

void Update_right ( int w , int i ){
    if( w==tr[i].l && w==tr[i].r )tr[i].limr++;
    else {
        QAQ mid = (tr[i].l + tr[i].r) >> 1 ;
        if( w>mid )Update_right( w , i<<1|1);else
        if( w<=mid)Update_right( w , i<<1 );
        tr[i].limr = tr[i<<1].limr + tr[i<<1|1].limr ;
    }
}

QAQ Query_left ( int q ,int w ,int i ){
    if( q<=tr[i].l && w>=tr[i].r )return tr[i].liml ;
    else {
        QAQ mid = (tr[i].l + tr[i].r) >> 1 ;
        if ( q>mid )return Query_left ( q , w , i<<1|1);
        else if ( w<=mid ) return Query_left ( q , w , i<<1);
        else return Query_left ( q , w , i<<1|1)+Query_left ( q , w , i<<1);
    }
}

QAQ Query_right ( int q ,int w ,int i ){
    if( q<=tr[i].l && w>=tr[i].r )return tr[i].limr ;
    else {
        QAQ mid = (tr[i].l + tr[i].r) >> 1 ;
        if ( q>mid )return Query_right ( q , w , i<<1|1);
        else if ( w<=mid ) return Query_right ( q , w , i<<1);
        else return Query_right ( q , w , i<<1|1)+Query_right ( q , w , i<<1);
    }
}

int main(){
    int N,M,op,ll,rr ;
    scanf("%d %d",&N,&M);
    Build_Tree ( 1 , N , 1 ) ;
    while(M--){
        scanf("%d%d%d",&op,&ll,&rr);
        if( op==1 ){
            Update_left ( ll , 1);
            Update_right ( rr , 1 );
        }
        else {
            QAQ ans = Query_left( 1 , rr , 1);
            if (ll!=1)ans-=Query_right(1 , ll-1 , 1);
            printf("%I64d\n",ans);
        }
    }
    return 0 ;
}

Horizontal Rule

线段树括号法

虽然说可以用线段树做，但还是树状数组比较短
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<string>
int t1[50001],t2[50001],n,m,k,l,r,ans;
int main()
{
scanf("%d%d",&n,&m);
while(m--)
{
scanf("%d%d%d",&k,&l,&r);
if(k==1)
{
for(int i=l;i<=n;i+=(i&((~i)+1)))
++t1[i];
for(int i=r;i<=n;i+=(i&((~i)+1)))
++t2[i];
}
else
{
ans=0;
for(int i=r;i;i-=(i&((~i)+1)))
ans+=t1[i];
for(int i=l-1;i;i-=(i&((~i)+1)))
ans-=t2[i];
printf("%d\n",ans);
}
}
return 0;
}

树状数组还是很牛逼的

记录信息
评测状态 Accepted
题目 P1448 校门外的树
递交时间 2015-10-11 16:36:36
代码语言 C++
评测机 VijosEx
消耗时间 1012 ms
消耗内存 916 KiB
评测时间 2015-10-11 16:36:37
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 916 KiB, score = 1
测试数据 #1: Accepted, time = 0 ms, mem = 916 KiB, score = 1
测试数据 #2: Accepted, time = 62 ms, mem = 916 KiB, score = 1
测试数据 #3: Accepted, time = 78 ms, mem = 916 KiB, score = 1
测试数据 #4: Accepted, time = 156 ms, mem = 916 KiB, score = 1
测试数据 #5: Accepted, time = 140 ms, mem = 916 KiB, score = 1
测试数据 #6: Accepted, time = 140 ms, mem = 916 KiB, score = 1
测试数据 #7: Accepted, time = 140 ms, mem = 916 KiB, score = 1
测试数据 #8: Accepted, time = 140 ms, mem = 912 KiB, score = 1
测试数据 #9: Accepted, time = 156 ms, mem = 916 KiB, score = 1
Accepted, time = 1012 ms, mem = 916 KiB, score = 10
代码
#include <iostream>
#include <stdio.h>
using namespace std;
int h[50010],t[50010];
int n,k;
void add(int a[],int k)
{
while(k<=n){
a[k]++;
k+=k&(-k);
}
}
int search(int a[],int k)
{
int tot=0;
while(k){
tot+=a[k];
k-=k&(-k);
}
return tot;
}
int main()
{

scanf("%d%d",&n,&k);
for(int i=1;i<=k;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(a==1){
add(h,b);
add(t,c);
}
else printf("%d\n",search(h,c)-search(t,b-1));
}
return 0;
}

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;

int n , m;
int sta;
int t , p;
int i;
int a[ 50000 + 10 ];
int b[ 50000 + 10 ];

int lowbit( int x )
{
return x & ( -x );
}

void modify( int q , int delta )
{
while( q <= n )
{
a[ q ] += delta;
q += lowbit( q );
}
return;
}

void add( int q , int delta )
{
while( q <= n )
{
b[ q ] += delta;
q += lowbit( q );
}
return;
}

int sum( int q )
{
int ans = 0;
while( q > 0 )
{
ans += a[ q ];
q -= lowbit( q );
}
return ans;
}

int value( int q )
{
int ans = 0;
while( q > 0 )
{
ans += b[ q ];
q -= lowbit( q );
}
return ans;
}

int main()
{
scanf( "%d %d" , &n , &m );
for( i = 0 ; i < m ; i++ )
{
scanf( "%d %d %d" , &sta , &t , &p );
if( sta == 1 )
{
modify( t , 1 );
modify( p , -1 );
add( t , 1 );
}
else
printf( "%d\n" , sum( t - 1 ) + value( p ) - value( t - 1 ) );
}
return 0;
}

var
a:array[1..50000]of longint;
n,m,i,j,s,b,c,max:longint;
begin
read(n,m);
fillchar(a,sizeof(a),0);
for i:=1 to m do
begin
read(s,b,c);
if s=1 then for j:=b to c do inc(a[j])
else begin
max:=0;
for j:=b to c do
if a[j]>max then max:=a[j];
writeln(max);
end;
end;

求解为什么我暴力只过一个点其余的都WA了，是题意我搞错了吗？？？？
end.

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

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

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

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

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

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

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

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

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

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

Accepted, time = 3602 ms, mem = 4192 KiB, score = 10

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<math.h>
#include<cstdlib>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,sz=0,l[500500][2];
int a,b,k;
void work()
{
int tem=0;
for(int i=0;i<sz;i++)
if(l[i][0]<=b&&l[i][1]>=a)tem++;
printf("%d\n",tem);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&k,&a,&b);
if(k==2)work();
else l[sz++][0]=min(a,b),l[sz-1][1]=max(a,b);
}
//system("pause");
return 0;
}

数据太弱，纯暴力枚举每一次植树是否对所询问区间有影响

好慢！！~~~：
编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 828 KiB, score = 1
测试数据 #1: Accepted, time = 0 ms, mem = 824 KiB, score = 1
测试数据 #2: Accepted, time = 0 ms, mem = 828 KiB, score = 1
测试数据 #3: Accepted, time = 15 ms, mem = 828 KiB, score = 1
测试数据 #4: Accepted, time = 15 ms, mem = 828 KiB, score = 1
测试数据 #5: Accepted, time = 0 ms, mem = 828 KiB, score = 1
测试数据 #6: Accepted, time = 3 ms, mem = 832 KiB, score = 1
测试数据 #7: Accepted, time = 0 ms, mem = 824 KiB, score = 1
测试数据 #8: Accepted, time = 3 ms, mem = 828 KiB, score = 1
测试数据 #9: Accepted, time = 15 ms, mem = 824 KiB, score = 1
Accepted, time = 66 ms, mem = 832 KiB, score = 10

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std ;

#define MAXN 50010
#define lowbit( x ) ( ( - x ) & x )

struct Bit {
int a[ MAXN ] , N ;
void Init( int _N ) {
N = _N ; memset( a , 0 , sizeof( a ) ) ;
}
void Add( int x , int y ) {
for ( int i = x ; i <= N ; i += lowbit( i ) ) a[ i ] += y ;
}
int Sum( int x ) {
int rec = 0 ;
for ( ; x ; x -= lowbit( x ) ) rec += a[ x ] ;
return rec ;
}
} b1 , b2 ;

int n , m ;

void getint( int &t ) {
int ch ;
for ( ch = getchar( ) ; ! ( ch >= '0' && ch <= '9' ) ; ch = getchar( ) ) ;
t = ch - '0' ;
for ( ch = getchar( ) ; ch >= '0' && ch <= '9' ; ch = getchar( ) ) t *= 10 , t += ch - '0' ;
}

void putint( int t ) {
if ( ! t ) putchar( '0' )
; else {
int ans[ 20 ] ;
ans[ 0 ] = 0 ;
for ( ; t ; t /= 10 ) ans[ ++ ans[ 0 ] ] = t % 10 ;
for ( int i = ans[ 0 ] ; i ; i -- ) putchar( '0' + ans[ i ] ) ;
}
putchar( '\n' );
}

int main( ) {
getint( n ) , getint( m ) ;
b1.Init( n ) , b2.Init( n ) ;
while ( m -- ) {
int x , y , z ;
getint( x ) , getint( y ) , getint( z ) ;
if ( x == 1 ) b1.Add( y , 1 ) , b2.Add( z , 1 ) ;
else putint( b1.Sum( z ) - b2.Sum( y - 1 ) ) ;
}
return 0 ;
}

线段树解决，记录suml与sumr

树状数组40行

├ 测试数据 01：答案正确... (0ms, 972KB)

├ 测试数据 02：答案正确... (0ms, 972KB)

├ 测试数据 03：答案正确... (0ms, 972KB)

├ 测试数据 04：答案正确... (0ms, 972KB)

├ 测试数据 05：答案正确... (0ms, 972KB)

├ 测试数据 06：答案正确... (0ms, 972KB)

├ 测试数据 07：答案正确... (465ms, 972KB)

├ 测试数据 08：答案正确... (1184ms, 972KB)

├ 测试数据 09：答案正确... (3325ms, 972KB)

├ 测试数据 10：答案正确... (3325ms, 972KB)

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

Accepted / 100 / 8300ms / 972KB

虽然费时，但是我会告诉你我用的模拟吗？模拟啊！模拟啊！writeln！我本来都以为AC率就这么没了呢！！

线段树解。题目可以理解为求给定区间和多少已知区间相交。那么只需要求出与当前区间不相交的，再减去就好了。具体思路为记录每一个区间的开始点与终端。如果当前区间的终端小于某区间的开始点或当前区间的开始点大于某区间的终端，则该区间与当前区间不相交。

var a:array[0..200000,1..2]{1表示开始点，2表示终端} of longint;

n,m,i,x,y,all,mr,ml,le,ri,k:longint;

Procedure change(l,r,x,pos,num:longint);{记录每一个区间的开始点与终端}

begin

if (pos>r)or(pos=ml then exit(0);

if ml>r then exit(a[x,2]);

le:=searchle(l,(l+r)div 2,2*x);

ri:=searchle((l+r)div 2+1,r,2*x+1);

exit(le+ri);

end;

Function searchri(l,r,x:longint):longint;{寻找右侧不相交区间数}

var le,ri:longint;

begin

if r