清北学堂学习总结 day1 数据结构 练习

1.二叉搜索树

STL set直接做就可以了

2.树状数组+差分数列:

codevs 1081 线段树练习 2

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 大师 Master

题目描述 Description

给你N个数,有两种操作

1:给区间[a,b]的所有数都增加X

2:询问第i个数是什么?

输入描述 Input Description

第一行一个正整数n,接下来n行n个整数,再接下来一个正整数Q,表示操作的个数. 接下来Q行每行若干个整数。如果第一个数是1,后接3个正整数a,b,X,表示在区间[a,b]内每个数增加X,如果是2,后面跟1个整数i, 表示询问第i个位置的数是多少。

输出描述 Output Description

对于每个询问输出一行一个答案

样例输入 Sample Input

3

1

2

3

2

1 2 3 2

2 3

样例输出 Sample Output

5

数据范围及提示 Data Size & Hint

数据范围

1<=n<=100000

1<=q<=100000

代码:

#define N 100100
#include<iostream>
#include<cstdio>
using namespace std;
#include<cstring>
int a[N],b[N],n,q,l,r,x,p;
long long  tree[N];
void build_tree(int k,int m)
{
    while(k<=n)
    {
        tree[k]+=m;
        k+=((-k)&k);
    }
}
long long query(int k)
{
    long long ans=0;
    while(k)
    {
        ans+=tree[k];
        k-=((-k)&k);
    }
    return ans;
}
void input()
{
    scanf("%d",&n);
    a[0]=0;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        b[i]=a[i]-a[i-1];
        build_tree(i,b[i]);
    }
}
int main()
{
    input();
    scanf("%d",&q);
    for(int i=0;i<q;++i)
    {
        scanf("%d",&x);
        if(x==1)
        {
            scanf("%d%d%d",&l,&r,&p);
            build_tree(l,p);
            build_tree(r+1,-p);
        }
        else
        {
            scanf("%d",&p);
            cout<<query(p)<<endl;
        }
    }
    return 0;
}

3.ST表

Balanced Lineup

Time Limit: 5000MS   Memory Limit: 65536K
Total Submissions: 43893   Accepted: 20585
Case Time Limit: 2000MS

Description

For the daily milking, Farmer John‘s N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.

Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.

Input

Line 1: Two space-separated integers, N and Q
Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i 
Lines N+2..N+Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.

Output

Lines 1..Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.

Sample Input

6 3
1
7
3
4
2
5
1 5
4 6
2 2

Sample Output

6
3
0

题意:查询一个区间的最大值最小值,输出二者的差

#include<iostream>
#define N 50101
#include<cstdio>
#include<cstring>
using namespace std;
int hige[N],n,q,l,r;
#define K 17
int min_rmq[N][K+1];
int max_rmq[N][K+1];
int ff[(1<<K)+1];
void input()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i)
    scanf("%d",&hige[i]);
}
void pre_chuli()
{
    for(int i=1;i<=n;++i)
    {
        min_rmq[i][0]=hige[i];
        max_rmq[i][0]=hige[i];
    }
    for(int j=1;j<=K;++j)
      for(int i=1;i+(1<<j)-1<=n;++i)
      {
          min_rmq[i][j]=min(min_rmq[i][j-1],min_rmq[i+(1<<j-1)][j-1]);
          max_rmq[i][j]=max(max_rmq[i][j-1],max_rmq[i+(1<<j-1)][j-1]);
      }
    memset(ff,-1,sizeof(ff));
    ff[0]=0;
    for(int i=0;i<=K;++i)
    ff[1<<i]=i;
    for(int i=1;i<=(1<<K);++i)
    if(ff[i]==-1)
    ff[i]=ff[i-1];
}
int max_query(int l,int r)
{
    int t=ff[r-l+1];
    return max(max_rmq[l][t],max_rmq[r-(1<<t)+1][t]);
}
int min_query(int l,int r)
{
    int t=ff[r-l+1];
    return min(min_rmq[l][t],min_rmq[r-(1<<t)+1][t]);
}
int main()
{
    input();
    pre_chuli();
    for(int i=1;i<=q;++i)
    {
        scanf("%d%d",&l,&r);
        printf("%d\n",max_query(l,r)-min_query(l,r));
    }
    return 0;
}

4.trie树

cojs 173. 词链

★☆   输入文件:link.in   输出文件:link.out   简单对比
时间限制:1 s   内存限制:128 MB

【问题描述】
给定一个仅包含小写字母的英文单词表,其中每个单词最多包含 50 个字母。

如果一张由一个词或多个词组成的表中,每个单词(除了最后一个)都是排在它后面的单词的前缀,则称此表为一个词链。例如下面的单词组成了一个词链:


int 
integer

而下面的单词不组成词链:

integer 
intern

请在给定的单词表中取出一些词,组成最长的词链。最长的词链就是包含单词数最多的词链。

数据保证给定的单词表中,单词互不相同,并且单词按字典顺序排列。

【输入格式】

第一行一个整数 n ,表示单词表中单词数。

下接 n 行每行一个单词。

【输出格式】

一个整数,表示最长词链长度。

【输入输出样例】 
输入:
link.in
5
i
int
integer
intern
internet

输出:
link.out
4

【数据范围】

50% 的数据, n<=1000

100% 的数据, n<=10000

#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
#define N 10100
int n;
int ans=0;
int topt=0;
#define L 51
struct Trie{
    int nxt[26];
    int cnt;
}trie[L];
void dfs(int k,int pre_ans)
{/*dfs统计单词数目*/
    for(int i=0;i<26;++i)
      if(trie[k].nxt[i])
      {
          dfs(trie[k].nxt[i],pre_ans+trie[k].cnt);
      }
    ans=max(pre_ans+trie[k].cnt,ans);
}
void build(char *str)
{
    int now=0;
    while(*str)
    {
        if(!trie[now].nxt[*str-‘a‘])
        trie[now].nxt[*str-‘a‘]=++topt;
        now=trie[now].nxt[*str-‘a‘];
        str++;
    }
    trie[now].cnt++;/*建树*/
}
void input()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        char s[L];
        scanf("%s",s);
        build(s);
    }
    dfs(0,0);
    printf("%d\n",ans);
}
int main()
{
    freopen("link.in","r",stdin);
//    freopen("link.out","w",stdout);
    input();
//    fclose(stdin);fclose(stdout);
    return 0;
}

5.并查集--加权并查集

POJ   1182 食物链

Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 60173   Accepted: 17627

Description

动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B, B吃C,C吃A。 
现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。 
有人用两种说法对这N个动物所构成的食物链关系进行描述: 
第一种说法是"1 X Y",表示X和Y是同类。 
第二种说法是"2 X Y",表示X吃Y。 
此人对N个动物,用上述两种说法,一句接一句地说出K句话,这K句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。 
1) 当前的话与前面的某些真的话冲突,就是假话; 
2) 当前的话中X或Y比N大,就是假话; 
3) 当前的话表示X吃X,就是假话。 
你的任务是根据给定的N(1 <= N <= 50,000)和K句话(0 <= K <= 100,000),输出假话的总数。

Input

第一行是两个整数N和K,以一个空格分隔。 
以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。 
若D=1,则表示X和Y是同类。 
若D=2,则表示X吃Y。

Output

只有一个整数,表示假话的数目。

Sample Input

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

Sample Output

3

Source

noi 01

  1 /*Part I  - 权值(relation)的确定。
  2     我们根据题意,森林中有3种动物。A吃B,B吃C,C吃A。
  3     我们还要使用并查集,那么,我们就以动物之间的关系来作为并查集每个节点的
  4     权值。
  5     注意,我们不知道所给的动物(题目说了,输入只给编号)所属的种类。
  6     所以,我们可以用动物之间“相对”的关系来确定一个并查集。
  7     0 - 这个节点与它的父节点是同类
  8     1 - 这个节点被它的父节点吃
  9     2 - 这个节点吃它的父节点。
 10
 11     注意,这个0,1,2所代表的意义不是随便制定的,我们看题目中的要求。
 12     说话的时候,第一个数字(下文中,设为d)指定了后面两种动物的关系:
 13     1 - X与Y同类
 14     2 - X吃Y
 15
 16     我们注意到,当 d = 1的时候,( d - 1 ) = 0,也就是我们制定的意义
 17                 当 d = 2的时候,( d - 1 ) = 1,代表Y被X吃,也是我们指定的意义。
 18     所以,这个0,1,2不是随便选的
 19
 20
 21     Part II - 路径压缩,以及节点间关系确定
 22     确定了权值之后,我们要确定有关的操作。
 23     我们把所有的动物全初始化。
 24     struct Animal
 25     {
 26         int num; //该节点(node)的编号
 27         int parent; //该node的父亲
 28         int relation; //该node与父节点的关系,0同类,1被父节点吃,2吃父节点
 29     }; Animal ani[50010];
 30         初始化为
 31         For i = 0 to N do
 32             ani[i].num = i;
 33             ani[i].parent = i;
 34             ani[i].relation = 0 ; //自己和自己是同类
 35         End For
 36
 37         (1)路径压缩时的节点算法
 38         我们设A,B,C动物集合如下:(为了以后便于举例)
 39         A = { 1 , 2 , 3 ,4 ,5 }
 40         B = { 6 , 7 , 8 ,9 ,10}
 41         C = { 11, 12, 13,14,15}
 42         假如我们已经有了一个集合,分别有3个元素
 43         SET1 = {1,2},我们规定集合中第一个元素为并查集的“代表”
 44         假如现在有语句:
 45         2 2 6
 46         这是一句真话
 47         2是6的父亲
 48          ani[6].parent = 2;
 49          ani[6].relation = 1;
 50         那么,6和1的关系如何呢?
 51          ani[2].parent = 1;
 52          ani[2].relation = 0;
 53         我们可以发现6与2的关系是 1.
 54         通过穷举我们可以发现
 55         ani[now].parent = ani[ani[now].parent].parent;
 56         ani[now].relation = ( ani[now].relation + ani[now.parent].relation ) % 3;
 57         这个路径压缩算法是正确的
 58         关于这个路径压缩算法,还有一点需要注意的地方,我们一会再谈
 59         注意,根据当前节点的relation和当前节点父节点的relation推出
 60         当前节点与其父节点的父节点的relation这个公式十分重要!!
 61         它推不出来下面都理解不了!!自己用穷举法推一下:
 62         好吧,为了方便伸手党,我给出穷举过程
 63                 i      j
 64         爷爷  父亲  儿子  儿子与爷爷
 65                0      0       (i + j)%3 = 0
 66                0      1       (i + j)%3 = 1
 67                0      2       (i + j)%3 = 2
 68                1      0       (i + j)%3 = 1
 69                1      1       (i + j)%3 = 2
 70                1      2       (i + j)%3 = 0
 71                2      0       (i + j)%3 = 2
 72                2      1       (i + j)%3 = 0
 73                2      2       (i + j)%3 = 1
 74         嗯,这样可以看到,( 儿子relation + 父亲relation ) % 3 = 儿子对爷爷的relation
 75         这就是路径压缩的节点算法
 76         (2) 集合间关系的确定
 77         在初始化的时候,我们看到,每个集合都是一个元素,就是他本身。
 78         这时候,每个集合都是自洽的(集合中每个元素都不违反题目的规定)
 79         注意,我们使用并查集的目的就是尽量的把路径压缩,使之高度尽量矮
 80         假设我们已经有一个集合
 81         set1 = {1,2,7,10}
 82         set2 = {11,4,8,13},每个编号所属的物种见上文
 83         set3 = {12,5,4,9}
 84         现在有一句话
 85         2 13 2
 86         这是一句真话,X = 13,Y = 2
 87         我们要把这两个集合合并成一个集合。
 88         直接
 89         int a = findParent(ani[X]);
 90         int b = findParent(ani[Y]);
 91         ani[b].parent = a;
 92         就是把Y所在集合的根节点的父亲设置成X所在集合的根节点。
 93         但是,但是!!!!
 94         Y所在集合的根结点与X所在集合的根节点的关系!!!要怎么确定呢?
 95         我们设X,Y集合都是路径压缩过的,高度只有2层
 96         我们先给出计算的公式
 97         ani[b].relation = ( 3 - ani[Y].relation + ( d - 1 ) + ani[X].relation) % 3;
 98         这个公式,是分三部分,这么推出来的
 99         第一部分,好理解的一部分:
100         ( d - 1 ) :这是X和Y之间的relation,X是Y的父节点时,Y的relation就是这个
101         3 - ani[Y].relation = 根据Y与根节点的关系,逆推根节点与Y的关系
102         这部分也是穷举法推出来的,我们举例:
103         j
104         子         父相对于子的relation(即假如子是父的父节点,那么父的relation应该是什么,因为父现在是根节点,所以父.relation = 0,我们只能根据父的子节点反推子跟父节点的关系)
105          0             ( 3 - 0 ) % 3 = 0
106          1(父吃子)   ( 3 - 1 ) % 3 = 2 //父吃子
107          2(子吃父)    ( 3 - 2 ) % 3 = 1 //子吃父,一样的哦亲
108         ——————————————————————————————————————————————————————
109         我们的过程是这样的:
110         把ani[Y],先连接到ani[X]上,再把ani[Y]的根节点移动到ani[X]上,最后,把ani[Y]的根节点移动到ani[X]的根节点上,这样算relation的
111         还记得么,如果我们有一个集合,压缩路径的时候父子关系是这么确定的
112         ani[爷爷].relation = ( ani[父亲].relation + ani[儿子].relation ) % 3
113         我们已知道,( d - 1 )就是X与Y的relation了
114         而 (3 - ani[Y].relation)就是 以Y为根节点时,他的父亲的relation
115         那么
116         我们假设把Y接到X上,也就说,现在X是Y的父亲,Y原来的根节点现在是Y的儿子
117           Y的relation   +     ani[Y]根节点相对于ani[Y]的relation
118         ( ( d - 1 )         +    ( 3 - ani[Y].relation) ) % 3
119         就是ani[Y]的父亲节点与ani[X]的relation了!
120
121         那么,不难得到,ani[Y]的根节点与ani[X]根节点的关系是:
122         ( ( d - 1 ) + ( 3 - ani[Y].relation) + ani[X].relation ) % 3 ->应用了同余定理
123         注意,这个当所有集合都是初始化状态的时候也适用哦
124         还是以最开头我们给的三个集合(分别代表三个物种)为例
125         2 1 6
126         带入公式
127         ani[6].relation = ( ( 2 - 1 ) + ( 3 - 0 ) + 0 ) % 3 = 1
128         也就是,6被1吃
129     Part III - 算法正确性的证明
130         首先,两个自洽的集合,合并以后仍然是自洽的
131         这个不难想吧,数学上有个什么对称性定理跟他很像的。
132         如果理解不了,就这么想!!
133         当set1和set2合并之后,set2的根节点得到了自己关于set1根节点的
134         正确relation值,变成了set1根节点的儿子,那么
135         set2的所有儿子只要用
136         ( ani[X].relation + ani[Y].relation ) % 3就能得到自己正确的relation值了
137         所以说,针对不在同一集合的两个元素的话,除非违背了(2)和(3),否则永远是真的
138         (无论这句话说的是什么,我们都可以根据所给X,Y推出两个子节点之间应有的关系,这个关系一确定,所有儿子的关系都可以确定)
139
140         其实所有的不同集合到最后都会被合并成一个集合的。
141         我们只要在一个集合中找那些假话就可以了。
142         首先,如何判断
143         1 X Y是不是假话。//此时 d = 1
144         if ( X 和 Y 不在同一集合)
145             Union(x,y,xroot,yroot,d)
146         else
147             if x.relation != y.relation  ->假话
148         其次,如何判断
149         2 X Y是不是假话 //此时d = 2
150         if ( X 和 Y 不在同一集合)
151             Union(x,y,xroot,yroot,d)
152         else
153             (ani[y].relation + 3 - ani[x].relation ) % 3 != 1 ->假话
154         这个公式是这么来的:
155         3 - ani[x].relation得到了根节点关于x的relation
156         ani[y] + 3 - ani[x].relation得到了y关于x的relation
157         所以,只要y关于x的relation不是1,就是y不被x吃的话,这句话肯定是假话!
158
159         (2)路径压缩要特别注意的一点(错在这里,要检讨自己)
160             路径压缩的时候,记得要
161             先findParent,再给当前节点的relation赋值。
162             否则有可能因为当前节点的父节点的relation不正确而导致错的稀里哗啦。
163             例子:
164             set1 = {1,2,7,10}
165             set2 = {3,4,8,11}
166             set3 = {12,5,14,9}
167             Union(1,3,1,3,1)
168             Union(3,12,3,12,2)
169             1 5 1
170             算5的relation
171             如果不先更新parent的relation,算出来应该是
172             ( 3 - 0 + 0 + 1 ) % 3 = 1,5被1吃,显然不对
173             这里面,+ 0的那个0是指根节点 12 的relation(未更新,这里的0是指12与11的relation)
174             如果更新完了的话,应该是
175             ( 3 - 0 + 2 + 1 ) % 3 = 0 ,5与1是同一物种,对了
176             这里面的 2 是更新节点12的relation(12与1的relation)*/
177 #define N 50100
178 int father[N];
179 #include<iostream>
180 #include<cstdio>
181 int val[N];
182 #include<cstring>
183 using namespace std;
184 int n,k;
185 int d,x,y;
186 int ans=0;
187 int find(int k)
188 {
189     if(k!=father[k])
190     {
191         int tmp=father[k];
192         father[k]=find(father[k]);
193         val[k]=(val[k]+val[tmp])%3;/*路径压缩的过程,利用儿子与父亲,父亲与爷爷的关系,求出儿子与爷爷的关系*/
194     }
195     return father[k];/*注意这里是return  father[k],而不是k,因为这是路径压缩,father[k]都指到了根节点,而k没有*/
196 }
197 int main()
198 {
199     scanf("%d%d",&n,&k);
200     for(int i=1;i<=n;++i)
201     father[i]=i,val[i]=0;/*初始化并查集,val表示儿子与父亲的关系*/
202     for(int i=0;i<k;++i)
203     {
204         scanf("%d%d%d",&d,&x,&y);
205         if(x>n||y>n)
206         {
207             ans++;
208             continue;
209         }
210         if(d==1)
211         {
212             if(find(x)==find(y))
213             {
214                 if(val[x]!=val[y])
215                 ans++;
216             }
217             else
218             {
219                 val[father[x]]=(val[y]-val[x]+3)%3;
220                 father[father[x]]=father[y];
221              }
222         }
223         else
224         {
225             if(x==y)
226             {
227                 ans++;
228                 continue;
229             }
230             if(find(x)==find(y))
231             {
232                 if(val[x]!=(val[y]+1)%3)/*y的边指向x,x吃y,y离着根节点近*/
233                 ans++;
234             }
235             else{
236
237             //    father[father[x]]=father[y];/*放在上面是不对的,当初值的时候father[x]=x,father[y]=y,当把这个语句放到上面的时候,下面的语句就成了val[y]的赋值了,而不是val‘[x]的赋值,因为这个时候val[y]应该是0*/
238                 val[father[x]]=(val[y]+1-val[x]+3)%3;
239                father[father[x]]=father[y];
240             }
241         }
242     }
243     cout<<ans<<endl;
244     return 0;
245  } 

6.线段树

3304 水果姐逛水果街Ⅰ

时间限制: 2 s

空间限制: 256000 KB

题目等级 : 钻石 Diamond

题解

题目描述 Description

水果姐今天心情不错,来到了水果街。

水果街有n家水果店,呈直线结构,编号为1~n,每家店能买水果也能卖水果,并且同一家店卖与买的价格一样。

学过oi的水果姐迅速发现了一个赚钱的方法:在某家水果店买一个水果,再到另外一家店卖出去,赚差价。

就在水果姐窃喜的时候,cgh突然出现,他为了为难水果姐,给出m个问题,每个问题要求水果姐从第x家店出发到第y家店,途中只能选一家店买一个水果,然后选一家店(可以是同一家店,但不能往回走)卖出去,求每个问题中最多可以赚多少钱。

输入描述 Input Description

第一行n,表示有n家店

下来n个正整数,表示每家店一个苹果的价格。

下来一个整数m,表示下来有m个询问。

下来有m行,每行两个整数x和y,表示从第x家店出发到第y家店。

输出描述 Output Description

有m行。

每行对应一个询问,一个整数,表示面对cgh的每次询问,水果姐最多可以赚到多少钱。

样例输入 Sample Input

10
2 8 15 1 10 5 19 19 3 5 
4
6 6
2 8
2 2
6 3

样例输出 Sample Output

0
18
0
14

数据范围及提示 Data Size & Hint

0<=苹果的价格<=10^8

0<n,m<=200000

分类标签 Tags

划分型DP 动态规划 区间型DP 线段树 树结构

#include<iostream>
using namespace std;
#include<cstdio>
#define lch 2*k
#define rch 2*k+1
#define N 200001
#define INF 1<<30
struct node{
    int min_,max_,max_val1,max_val2;
    node(){min_=INF;max_=max_val1=max_val2=0;}
}tree[N*2+100];
int t=0;
int n,a[N],m;
void input()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    scanf("%d",&a[i]);
}
void update(int k)
{
    tree[k].min_=min(tree[lch].min_,tree[rch].min_);
    tree[k].max_=max(tree[lch].max_,tree[rch].max_);
    tree[k].max_val1=max(tree[lch].max_val1,max(tree[rch].max_val1,tree[rch].max_-tree[lch].min_));
    tree[k].max_val2=max(tree[lch].max_val2,max(tree[rch].max_val2,tree[lch].max_-tree[rch].min_));
}
void build_tree(int k,int l,int r)
{
    if(l==r-1)
    {
        tree[k].max_=a[l];
        tree[k].max_val1=tree[k].max_val2=0;
        tree[k].min_=a[l];
        return ;
    }
    int mid=(l+r)/2;
    build_tree(lch,l,mid);
    build_tree(rch,mid,r);
    update(k);
}
node query(int k,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)
    {
        return tree[k];
    }
    node ans;
    int mid=(l+r)/2;
    node b1;
    if(x<mid)
    {
        ans=query(lch,l,mid,x,y);
    }
    if(y>mid)
    {
        b1=query(rch,mid,r,x,y);
        ans.max_=max(ans.max_,b1.max_);
        ans.min_=min(ans.min_,b1.min_);
        ans.max_val1=max(ans.max_val1,max(b1.max_val1,b1.max_-ans.min_));
    }
    return ans;
}
node ex_query(int k,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)
    {
        return tree[k];
    }
    node ans;
    int mid=(l+r)/2;
    node b1;
    if(x<mid)
    {
        ans=query(lch,l,mid,x,y);
    }
    if(y>mid)
    {
        b1=query(rch,mid,r,x,y);
        ans.max_=max(ans.max_,b1.max_);
        ans.min_=min(ans.min_,b1.min_);
        ans.max_val2=max(ans.max_val2,max(b1.max_val2,ans.max_-b1.min_));
    }
    return ans;
}
int main()
{
    input();
    build_tree(1,1,n+1);
    scanf("%d",&m);
    int x,y;
    while(m--)
    {
        scanf("%d%d",&x,&y);

        node ans;
        if(x<=y)
        {
            ans=query(1,1,n+1,x,y+1);
            printf("%d\n",ans.max_val1);
        }
        else{
            ans=ex_query(1,1,n+1,y,x+1);
            printf("%d\n",ans.max_val2);
        }

    }
    return 0;
}

代码:

7.

时间: 05-05

清北学堂学习总结 day1 数据结构 练习的相关文章

清北学堂2017NOIP冬令营入学测试 P4744 A’s problem(a)

清北学堂2017NOIP冬令营入学测试 P4744 A's problem(a) 时间: 1000ms / 空间: 655360KiB / Java类名: Main 背景 冬令营入学测试题,每三天结算一次成绩.参与享优惠 描述 这是一道有背景的题目,小A也是一个有故事的人.但可惜的是这里纸张太小,小A无法把故事详细地说给大家听.可能小A自己也讲不清楚自己的故事,因为如果讲清了,也就没有这道题目了-- 小A的问题是这个样子,它找到了n份不同的工作,第i份工作每个月有ai的工资,每份工作需要小A每天

2016.10.29 清北学堂NOIP冲刺班Day1 AM 考试总结

成绩:满分300,我得了200, 1:90//前两个题目都是模拟,没用到什么其他算法,第一题有可能少考虑了一点细节 2:100 3:10//感觉是个DP,但是毫无思路,只打了个普通背包,10分而已. 题目+数据:http://pan.baidu.com/s/1bpj3SR1 下面是我的代码: 这个题目中我为了得到部分分,而特别判断了几组数据. T1: 1 /* 2 以后一定要仔细读数据范围,一定要. 3 数据范围中:20%的数据,只有秒数可能不同,言外之意就是可能相同. 4 而我的程序因为没有考

洛谷P1080 [NOIP2012提高组D1T2]国王游戏 [2017年5月计划 清北学堂51精英班Day1]

P1080 国王游戏 题目描述 恰逢 H 国国庆,国王邀请 n 位大臣来玩一个有奖游戏.首先,他让每个大臣在左.右 手上面分别写下一个整数,国王自己也在左.右手上各写一个整数.然后,让这 n 位大臣排 成一排,国王站在队伍的最前面.排好队后,所有的大臣都会获得国王奖赏的若干金币,每 位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右 手上的数,然后向下取整得到的结果. 国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序, 使得获得奖赏最多的大

关于树的一点学习【清北学堂】

我主要在这里讲的是树的直径求法和树的重心求法 树的直径,指的就是树上距离最远两点间的一条路径. 求树的直径的方法是,首先我任选一个点,找到与它距离最远的点,记为s 再以s为起点找离他最远的点,记为v s到v的路径即为树的直径 树的重心指的就是树上一个节点,把这个节点挖掉之后,剩下很多联通块  而重心就让这些联通块中最大的那个最小 树的重心有两种求法 一种是枚举每一个点 看把他挖掉之后会发生什么 第二种是DFS求出每个节点联通块大小 可能有人说每个节点不都连着整个树么 所以说这个联通块是算上节点自

P2327 [SCOI2005]扫雷 [2017年5月计划 清北学堂51精英班Day1]

P2327 [SCOI2005]扫雷 题目描述 输入输出格式 输入格式: 第一行为N,第二行有N个数,依次为第二列的格子中的数.(1<= N <= 10000) 输出格式: 一个数,即第一列中雷的摆放方案数. 输入输出样例 输入样例#1: 2 1 1 输出样例#1: 2 其实还是扫雷玩的少..知道思路之后很快 只需枚举前两个各自的情况,后面的各自便能够计算出来 注意几个细节(在代码里面) #include <iostream> #include <cstdio> #in

清北学堂 最大速度

最大速度 (maxv.pas/c/cpp) [问题描述] Ron的老爸的Flying Car出了些问题,现在必须要在地上跑到很大的速度才能飞起来,但是Flying Car飞起来的那一刻不能被麻瓜看到.为了确保安全飞起来,需要知道车到可以飞起来的地方时所能达到的最大速度.他的Flying Car一开始拥有一个初速度,移动一次增加速度1:因为车道很窄,宽度只有1,所以仅当要转向的方向有路时才能转,左转一次减少速度35,右转一次减少速度40,当前进.左转.右转都无路可走的时候,调头(连左转两次或连右转

清北学堂2017NOIP冬令营入学测试

P4744 A's problem(a) 时间: 1000ms / 空间: 655360KiB / Java类名: Main 背景 冬令营入学测试题,每三天结算一次成绩.参与享优惠 描述 这是一道有背景的题目,小A也是一个有故事的人.但可惜的是这里纸张太小,小A无法把故事详细地说给大家听.可能小A自己也讲不清楚自己的故事,因为如果讲清了,也就没有这道题目了-- 小A的问题是这个样子,它找到了n份不同的工作,第i份工作每个月有ai的工资,每份工作需要小A每天工作8小时,一周工作7天.小A想知道性价

清北学堂 逃亡的准备

  逃亡的准备 (hallows.pas/c/cpp)   [问题描述] 在<Harry Potter and the Deathly Hallows>中,Harry Potter他们一起逃亡,现在有许多的东西要放到赫敏的包里面,但是包的大小有限,所以我们只能够在里面放入非常重要的物品,现在给出该种物品的数量.体积.价值的数值,希望你能够算出怎样能使背包的价值最大的组合方式,并且输出这个数值,赫敏会非常地感谢你. [输入文件](hallows.in) (1)第一行有2个整数,物品种数n和背包装

清北学堂 站军姿

/*2bc*cosA=b^2+c^2-a^2 模拟计算 50分*/ #include<iostream> #include<cstdio> #include<cmath> using namespace std; const double t=3.1415926535898; int n; double a,b,c,x,y,z,x2,y2,z2,s,k,m,w,p; int main () { freopen ("standing.in","