136 条题解
-
2
Sky1231 (sky1231) LV 10 @ 4 年前
-
26 年前@
简单的模板题
开两个树状数组维护即可 -
13 年前@
-
04 个月前@
#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;}}
自己看吧 -
04 年前@
参考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,快读还是狠滴代码
-
04 年前@
树状数组解
-
07 年前@
左右括号法
线段树||树状数组......
不存在的
#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);
}
}
} -
08 年前@
JRX2015U43:树状数组。
http://blog.csdn.net/qq_31640513/article/details/61435432 -
08 年前@
#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;
} -
08 年前@
Horizontal Rule
线段树括号法
-
09 年前@
虽然说可以用线段树做,但还是树状数组比较短
#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;
} -
09 年前@
树状数组还是很牛逼的
记录信息
评测状态 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;
} -
010 年前@
#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;
} -
010 年前@
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. -
010 年前@
测试数据 #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;
}数据太弱,纯暴力枚举每一次植树是否对所询问区间有影响
-
011 年前@
好慢!!~~~:
编译成功测试数据 #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 ;
} -
011 年前@
线段树解决,记录suml与sumr
-
011 年前@
树状数组40行
-
012 年前@
├ 测试数据 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率就这么没了呢!!
-
012 年前@
线段树解。题目可以理解为求给定区间和多少已知区间相交。那么只需要求出与当前区间不相交的,再减去就好了。具体思路为记录每一个区间的开始点与终端。如果当前区间的终端小于某区间的开始点或当前区间的开始点大于某区间的终端,则该区间与当前区间不相交。
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