一个小问题
查看原帖
一个小问题
518232
Sternenlicht楼主2022/1/3 11:00

我用树状数组解这题,为什么用define定义lowbit函数会TLE

#define lowbit(x) x&-x

而自定义函数却不会

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

下面是我的代码,有哪位dalao能告诉我为什么

#include <map>
#include <queue>
#include <vector>
#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 50100
using namespace std;

int n,m;
int a[N],tree_max[N],tree_min[N];
int lowbit(int x)
{
	return x&-x;
}

void add(int x,int k)
{
    for (;x<=n;x+=lowbit(x))
    {
    	tree_max[x]=max(tree_max[x],k);
    	tree_min[x]=min(tree_min[x],k);
    }
}

int ask_max(int x,int y)
{
	if (y>x)
	{
		if (y-lowbit(y)>x)
		{
			return max(tree_max[y],ask_max(x,y-lowbit(y)));
		}
		else
		{
			return max(a[y],ask_max(x,y-1));
		}
	}
	return a[x];
}

int ask_min(int x,int y)
{
	if (y>x)
	{
		if (y-lowbit(y)>x)
		{
			return min(tree_min[y],ask_min(x,y-lowbit(y)));
		}
		else
		{
			return min(a[y],ask_min(x,y-1));
		}
	}
	return a[x];
}

int main()
{
    memset(tree_min,0x3f3f3f3f,sizeof(tree_min));
	scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        add(i,a[i]);
    }
    for (int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",ask_max(x,y)-ask_min(x,y));
    }
    return 0;
}
2022/1/3 11:00
加载中...