tyvj 1297:
比较简单的线段树。
#include <stdio.h>
int a[50010];
struct node
{
int l, r, min, max;
};
node tree[50010 * 3];
void build(int ll, int rr, int s)
{
tree[s].l = ll;
tree[s].r = rr;
while(ll == rr)
{
tree[s].min = tree[s].max = a[ll];
return ;
}
int mid = (ll + rr) / 2;
build(ll, mid, s * 2);
build(mid + 1, rr, s * 2 + 1);
tree[s].min = tree[s * 2].min < tree[s * 2 + 1].min ? tree[s * 2].min : tree[s * 2 + 1].min;
tree[s].max = tree[s * 2].max > tree[s * 2 + 1].max ? tree[s * 2].max : tree[s * 2 + 1].max;
}
int search1(int ll, int rr, int s)
{
if(tree[s].l == ll && tree[s].r == rr)
return tree[s].max;
if(ll >= tree[s * 2 + 1].l)
return search1(ll, rr, s * 2 + 1);
if(rr <= tree[s * 2].r)
return search1(ll, rr, s * 2);
int mid = (tree[s].l + tree[s].r) / 2;
int t1 = search1(ll, mid, s * 2);
int t2 = search1(mid + 1, rr, s * 2 + 1);
return t1 > t2 ? t1 : t2;
}
int search2(int ll, int rr, int s)
{
if(tree[s].l == ll && tree[s].r == rr)
return tree[s].min;
if(ll >= tree[s * 2 + 1].l)
return search2(ll, rr, s * 2 + 1);
if(rr <= tree[s * 2].r)
return search2(ll, rr, s * 2);
int mid = (tree[s].l + tree[s].r) / 2;
int t1 = search2(ll, mid, s * 2);
int t2 = search2(mid + 1, rr, s * 2 + 1);
return t1 < t2 ? t1 : t2;
}
int main (void)
{
int n, p;
while(scanf("%d %d", &n, &p) != EOF)
{
int i;
for(i = 1; i <= n; i++)
scanf("%d", &a[i]);
build(1, n, 1);
//for(i = 1; i <= n * 2; i++)
// printf("l = %d, r = %d, min = %d, max = %d\n", tree[i].l, tree[i].r, tree[i].min, tree[i].max);
while(p --)
{
int x, y;
scanf("%d %d", &x, &y);
printf("%d ", search1(x, y, 1));
printf("%d\n", search2(x, y, 1));
}
}
return 0;
}
tyvj 1491:
这题开始我是用位运算做的，但是怎么都过不了最后一组数据。
原因就是如果给的修改区间很长的话，用for循环一个个改也还是很耗时。
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
int a[100010];
int main (void)
{
int n, p, k = 0;
scanf("%d %d", &n, &p);
int x, y, z, i;
while(p --)
{
scanf("%d", &x);
if(x & 1)
{
scanf("%d %d", &y, &z);
for(i = y; i <= z; i++)
a[i] ^= 1;
}
else
{
scanf("%d", &y);
printf("%d\n", a[y]);
}
}
return 0;
}
然后运用了线段树，感觉学长说的挺有道理的，线段树可以很灵活的使用，主要要看你怎么运用。（ps：写线段树特别容易出错好烦恼）
这题的线段树，结构体中存放一个标志f，表示这个区间是否有被改过，修改的时候只要修改区间正好是线段树中某个结点所表示的区间时，将结点中的f更改，就可以返回，不用再递归到最底层。但是因为这道题查抄的是某一个位置元素的值(不是某个区间)，所以查找的时候，函数会递归到具体的那个元素上，然后再返回，在返回的过程中，只要所经过的结点的f是1，那么就将返回值改变，0改1，1改0，我是用全局变量实现的。
这题虽然查找的时候要递归到树的最底层，但是修改的时候挺省事的，特别是修改区间特别长的时候。
#include <stdio.h>
struct node
{
int l, r;
int f;
};
node tree[100010 * 3];
int val;
void build(int ll, int rr, int s)
{
tree[s].l = ll;
tree[s].r = rr;
tree[s].f = 0;
while(ll == rr)
return ;
int mid = (ll + rr) / 2;
build(ll, mid, s * 2);
build(mid + 1, rr, s * 2 + 1);
}
void modify(int ll, int rr, int s)
{
if(tree[s].l == ll && tree[s].r == rr)
{
tree[s].f ^= 1;
return;
}
if(ll >= tree[s * 2 + 1].l)
return modify(ll, rr, s * 2 + 1);//注意return = =
if(rr <= tree[s * 2].r)
return modify(ll, rr, s * 2);
int mid = (tree[s].l + tree[s].r) / 2;
modify(ll, mid, s * 2);
modify(mid + 1, rr, s * 2 + 1);
}
void search(int x, int s)
{
if(tree[s].l == x && tree[s].r == x)
{
if(tree[s].f)
val ^= 1;//如果f是1，那么就改变val的值
return;
}
int mid = (tree[s].l + tree[s].r) / 2;
if(x <= mid)
search(x, s * 2);
if(x > mid)
search(x, s * 2 + 1);
if(tree[s].f)
val ^= 1;//改变
}
int main (void)
{
int n, p, k;
while(scanf("%d %d", &n, &p) != EOF)
{
int i;
build(1, n, 1);
int k, x, y;
while(p --)
{
scanf("%d", &k);
if(k == 1)
{
scanf("%d %d", &x, &y);
modify(x, y, 1);
}
else
{
scanf("%d", &x);
val = 0;//最初元素的值都是1
search(x, 1);
printf("%d\n", val);
}
}
}
return 0;
}