草庐IT

c++ - 具有惰性传播时间限制问题的线段树

coder 2024-02-25 原文

以下是http://www.spoj.pl/problems/LITE/的实现使用具有惰性传播的线段树。我是分割树的新手，我不明白为什么我会得到 TLE。有人可以看看它并帮助我纠正我的错误吗？

#include <iostream>
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX 100000
using namespace std;
int M[2*MAX+1];
int flag[2*MAX+1];
int count;
void refresh(int begin,int end,int n)
{
    M[n] = end-begin+1 - M[n];
    flag[n]=0;
    flag[n*2] =!flag[n*2];
    flag[n*2+1] =!flag[n*2+1];
}
void update(int begin,int end,int i,int j,int n=1)
{
    if(flag[n])
    {
        refresh(begin,end,n);
    }
    if(begin>=i && end<=j)
    {
        if(!flag[n])
        {
            refresh(begin,end,n);
        }
        flag[n] = 0;
        return;
    }
    else if(begin>=end)
    {
        return;
    }
    else
    {
        int mid = (begin+end)>>1;
        if(i<=mid)
        {
            update(begin,mid,i,j,n*2);
        }
        if(j>mid)
        {
            update(mid+1,end,i,j,n*2+1);
        }
        if(flag[2*n])
        {
            refresh(begin,mid,2*n);
        }
        if(flag[2*n+1])
        {
            refresh(mid+1,end,2*n+1);
        }
        M[n] = M[n*2]+ M[n*2+1];
    }
}
int query(int begin,int end,int i,int j,int n=1)
{
    if(flag[n])
    {
        refresh(begin,end,n);
    }
    if(begin>=i && end<=j)
    {
        return M[n];
    }
    if(begin>=end)
    {
        return 0;
    }
    int mid = (begin+end)>>1;
    int l=0,r=0;
    if(i<=mid)
    {
        l = query(begin,mid,i,j,n*2);
    }
    if(j>mid)
    {
        r = query(mid+1,end,i,j,n*2+1);
    }
    if(flag[2*n])
    {
        refresh(begin,mid,2*n);
    }
    if(flag[2*n+1])
    {
        refresh(mid+1,end,2*n+1);
    }
    M[n] = M[n*2]+ M[n*2+1];
    return l+r;
}
int main()
{
    memset(M,0,sizeof M);
    int n,m,a,b,c;
    scanf("%d%d",&n,&m);
    for(int i=0; i<m; i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        if(a==0)
        {
            update(1,n,b,c);
        }
        else
        {
            printf("%d\n",query(1,n,b,c));
        }
    }
    return 0;
}

最佳答案

M[node]^=1; 可能比 M[node] = (M[node]==0)?1:0; 更快，并且(begin+end)>>1 比 (begin/end)/2 快，但不是很相关

LE:尝试使递归函数内联是否会运行得更快。我认为它解开了递归几次并且工作得更快了一点。也许将参数作为引用发送会使它运行得更快，试试看。如果测试用例选择得当，你仍然不能用这种技巧通过测试，但有时它会有所帮助。

关于c++ - 具有惰性传播时间限制问题的线段树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6566826/

惰性ampbeginintendc++segment-treelazy-propagation

有关c++ - 具有惰性传播时间限制问题的线段树的更多相关文章

  1. ruby - 具有身份验证的私有(private) Ruby Gem 服务器 - 2

    我想安装一个带有一些身份验证的私有(private)Rubygem服务器。我希望能够使用公共(public)Ubuntu服务器托管内部gem。我读到了http://docs.rubygems.org/read/chapter/18.但是那个没有身份验证-如我所见。然后我读到了https://github.com/cwninja/geminabox.但是当我使用基本身份验证(他们在他们的Wiki中有)时，它会提示从我的服务器获取源。所以。如何制作带有身份验证的私有(private)Rubygem服务器？这是不可能的吗？谢谢。编辑:Geminabox问题。我尝试“捆绑”以安装新的gem..

  2. ruby - 在 64 位 Snow Leopard 上使用 rvm、postgres 9.0、ruby 1.9.2-p136 安装 pg gem 时出现问题 - 2

    我想为Heroku构建一个Rails3应用程序。他们使用Postgres作为他们的数据库，所以我通过MacPorts安装了postgres9.0。现在我需要一个postgresgem并且共识是出于性能原因你想要pggem。但是我对我得到的错误感到非常困惑当我尝试在rvm下通过geminstall安装pg时。我已经非常明确地指定了所有postgres目录的位置可以找到但仍然无法完成安装:$envARCHFLAGS='-archx86_64'geminstallpg--\--with-pg-config=/opt/local/var/db/postgresql90/defaultdb/po

  3. ruby - 通过 rvm 升级 ruby​​gems 的问题 - 2

    尝试通过RVM将RubyGems升级到版本1.8.10并出现此错误:$rvmrubygemslatestRemovingoldRubygemsfiles...Installingrubygems-1.8.10forruby-1.9.2-p180...ERROR:Errorrunning'GEM_PATH="/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/ruby-1.9.2-p180@global:/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/rub

  4. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  5. ruby - 通过 RVM (OSX Mountain Lion) 安装 Ruby 2.0.0-p247 时遇到问题 - 2

    我的最终目标是安装当前版本的RubyonRails。我在OSXMountainLion上运行。到目前为止，这是我的过程:已安装的RVM$\curl-Lhttps://get.rvm.io|bash-sstable检查已知(我假设已批准)安装$rvmlistknown我看到当前的稳定版本可用[ruby-]2.0.0[-p247]输入命令安装$rvminstall2.0.0-p247注意:我也试过这些安装命令$rvminstallruby-2.0.0-p247$rvminstallruby=2.0.0-p247我很快就无处可去了。结果:$rvminstall2.0.0-p247Search

  6. ruby - Fast-stemmer 安装问题 - 2

    由于fast-stemmer的问题，我很难安装我想要的任何ruby​​gem。我把我得到的错误放在下面。Buildingnativeextensions.Thiscouldtakeawhile...ERROR:Errorinstallingfast-stemmer:ERROR:Failedtobuildgemnativeextension./System/Library/Frameworks/Ruby.framework/Versions/2.0/usr/bin/rubyextconf.rbcreatingMakefilemake"DESTDIR="cleanmake"DESTDIR=

  7. ruby-on-rails - Ruby 检查日期时间是否为 iso8601 并保存 - 2

    我需要检查DateTime是否采用有效的ISO8601格式。喜欢:#iso8601?我检查了ruby​​是否有特定方法，但没有找到。目前我正在使用date.iso8601==date来检查这个。有什么好的方法吗？编辑解释我的环境，并改变问题的范围。因此，我的项目将使用jsapiFullCalendar，这就是我需要iso8601字符串格式的原因。我想知道更好或正确的方法是什么，以正确的格式将日期保存在数据库中，或者让ActiveRecord完成它们的工作并在我需要时间信息时对其进行操作。 最佳答案 我不太明白你的问题。我假设您想检查

  8. ruby - 安装 Ruby 时遇到问题(无法下载资源 "readline--patch") - 2

    当我尝试安装Ruby时遇到此错误。我试过查看this和this但无济于事➜~brewinstallrubyWarning:YouareusingOSX10.12.Wedonotprovidesupportforthispre-releaseversion.Youmayencounterbuildfailuresorotherbreakages.Pleasecreatepull-requestsinsteadoffilingissues.==>Installingdependenciesforruby:readline,libyaml,makedepend==>Installingrub

  9. ruby-on-rails - 将 Ruby 中的日期/时间格式化为 YYYY-MM-DD HH :MM:SS - 2

    这个问题在这里已经有了答案:Railsformattingdate(4个答案)关闭4年前。我想格式化Time.Now函数以显示YYYY-MM-DDHH:MM:SS而不是:“2018-03-0909:47:19+0000”该函数需要放在时间中.现在功能。require‘roo’require‘roo-xls’require‘byebug’file_name=ARGV.first||“Template.xlsx”excel_file=Roo::Spreadsheet.open(“./#{file_name}“,extension::xlsx)xml=Nokogiri::XML::Build

  10. ruby - 查找字符串中的内容类型(数字、日期、时间、字符串等) - 2

    我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s

随机推荐