/ Vijos / 题库 / 校门外的树 /

题解

135 条题解

  • 0
    @ 2008-09-17 12:17:01

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    用点树（线段树简化版）同程序提交3次AC，LORA

    顺便，第一次70第二次90

    再顺便，我用Writeln的

    最后顺便，本来想试试能不能一次AC的

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    树状数组WA了两次（丢脸，写错了）

    之后同程序两次AC，LORA，同样是WRITELN，第一次是80

    明显点树比树状数组快！

    不然就是我树状数组写太丑了

  • 0
    @ 2008-09-17 00:52:03

    2楼居然也是教主后援团的 你好你好 行贿行贿

  • 0
    @ 2008-10-12 15:15:03

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    开始以为遇上了诡异问题

    最后发现一直是用的write来输出

    最后加上一个writeln就好了。

  • 0
    @ 2008-09-16 21:14:32

    原来要write..

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2008-09-16 19:30:42

    同一个程序提交3次3个结果

    第一次40分，后6个点TLE

    第二次和第三次都70分，随机TLE3个点

    汗。。通过去的27个人是哪台测的？

  • 0
    @ 2008-09-16 18:33:00

    2008-9-16 17:40:01 )

  • 0
    @ 2008-09-16 18:14:10

    var

    i,j,k,n,m,v:longint;

    a,b,c,e:array[0..100000]of longint;

    d:array[0..100000,0..100000]of boolean;

    begin

    readln(n,m);

    fillchar(d,sizeof(d),false);

    v:=1;

    for i:=1 to m do

    begin

    read(a[i],b[i],c[i]);

    if a[i]=1

    then d[b[i],c[i]]:=true

    else begin

    for j:=1 to c[i] do

    if d[b[j],c[j]]

    then if ((b[i]=b[j]))or((c[i]>=b[j])and(c[i]

  • 0
    @ 2008-09-16 17:40:01

    太经典了write=AC

  • 0
    @ 2008-09-16 17:28:46

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    同样的机器，在无数次提交后~AC！

    WRITELN也能过

  • 0
    @ 2008-09-16 15:14:57

    只有Lora Temper能AC…………………………

  • 0
    @ 2008-09-16 13:11:36

    1、用write

    2、Lora Temper

    3、看一点RP

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2008-09-15 22:51:48

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    Lora~~~总算跑过了!!!

  • 0
    @ 2008-09-15 22:20:16

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    with Lora Temper

    AC的代价是降低2个百分点~~~

  • 0
    @ 2008-09-15 20:20:29

    ORZ fjxmlhx

  • 0
    @ 2008-09-15 16:44:30

    我是盲人！！！！！请说普通话！！汉语 ！！

  • 0
    @ 2008-09-16 23:16:12

    伟大的write!!!!!!!

    伟大的write!!!!!!!

    伟大的write!!!!!!!

    伟大的write!!!!!!!

    伟大的write!!!!!!!

    伟大的write!!!!!!!

    伟大的write!!!!!!!

    和评测机没有关系的，我在dolphin都ac

    来自： fjxmlhx

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

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

    ( 2008-9-15 7:48:42 )

    就这么做，我用线段树写的，不过ac不能。

    本机cena测ac共0.87s,最慢点0.15s，vj上交10次同样程序，80-70-50-80-60-70-80-80-70-70，全TLE

    另外查纪录发现：puppy上1人ac,lora上1人，其余9人ac全是tiger上的。。。

    另：本题已经成为VJ通过率第2低的题了，截至08.9.15。

    另：本机测试n=m=500000数据，1s内出解，我没什么好说得了。

    另：经过试验，即使将答案存在数组里最后一起输出也ac不能。

    最后给个很重要建议： （puppy victoria一样，dolphin更差，Lora Temper好一点）

    没

    遇

    到

    T

    i

    g

    e

    r

    就

    别

    交

    了

    ！

    以上纯属废话。。。提交10几次后终于AC with dolphin（？！）。。。令人难以置信，dolphin居然完成了puppy lora...没有完成的任务。

    原因在于：

    伟大的write!!!!!!

    伟大的write!!!!!!!

  • 0
    @ 2009-06-11 21:43:59

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    使用write的线段树

  • -1
    @ 2018-09-28 17:04:32

    #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;//树状数组模板题
    }

  • -1
    @ 2017-10-02 11:50:40

    容易发现答案为\(\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));
    }
}
  • -1
    @ 2016-08-09 09:34:51

    代码

    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.

校门外的树

信息

ID
1448
难度
6
分类
数据结构 | 线段树 点击显示
标签
递交数
2920
已通过
872
通过率
30%
被复制
6
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1