CodeChef

题目链接：https://vjudge.net/problem/CodeChef-ANDMIN

Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.

You are given an array of N integers. You should support the following queries on this array.

0 L R : Find the minimum integer in the range A_L, A_L+1, ..., A_R.
1 L R X : You should apply the assignment A[i] = A[i] & X, for all indices i in range [L, R], where & denotes bitwise AND operation.

Input

First line of the input contains two space separated integers N and Q.

Second line contains N integer numbers denoting array A.

In the next Q lines, each contain one of the queries described above.

Output

For each query of the type 0, output a single line containing the answer of the query.

Constraints

1 ≤ N, Q ≤ 10⁵
1 ≤ A_i, X ≤ 10⁹
1 ≤ L ≤ R ≤ N

Example

题意：

给出一个序列。有两种操作：0 L R，查询区间 [L, R]的最小值，1 L R X，对区间[L,R]中的每个数与x作与操作。

题解：

1.线段树的应用。可知对于一个int类型的值，最少只需做31次与操作，每一位上的值都全部为0。

2.构架线段树，线段树中的每个结点，除了记录当前段的最小值之外，还需记录一个状态，这个状态即：这一段中，有哪些位是为1的。当此段的这个位为1，且x的这个位为0，那么就可以继续往下更新，把这个段中的这个位置为0；否则，当此段的这个位为0，而x的这个位为0，那么就无需往下更新了，因为做的是无用功。

反思：

1.自己开始时的想法是：如果这一段的数不全为0，那么就往下更新，因为期望着在如若干操作之后，这些区间的值都会变成0，那么时间限制应该不成为题。然而这只是很幼稚的想法，如果x都是1111111111，那岂不是每一次都要往下更新到根节点，但值又不发生任何改变，即做了很多无用功。

2.计算机都讲究效率，我们想只做有用功。所以，就必须清楚哪些是有用功，哪些是无用功。对于此题，如果x不能改变当前段的任何一个值，那么执行它就是无用功了。所以，在线段树的每个节点中，记录有哪些位的值为1，当x的此位也为1，那么次操作就是有用功，否则是无用功。

3.线段树的结点，就是记录当前段，或者说当前集合的公共信息，常见是最大最小值、和，当然还可以是很多天马行空的信息，要大胆想。

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <vector>
 7 #include <queue>
 8 #include <stack>
 9 #include <map>
10 #include <string>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 const double EPS = 1e-8;
15 const int Int_Max = (1<<31)-1;
16 const int INF = 2e9;
17 const LL LNF = 2e18;
18 const int MAXN = 1e5+10;
19 
20 int minv[MAXN<<2], state[MAXN<<2];
21 void push_up(int u)
22 {
23     minv[u] = min(minv[u*2], minv[u*2+1]);
24     state[u] = state[u*2]|state[u*2+1];     //信息集合
25 }
26 
27 void build(int u, int l, int r)
28 {
29     if(l==r)
30     {
31         scanf("%d", &minv[u]);
32         state[u] = minv[u];
33         return;
34     }
35 
36     int mid = (l+r)>>1;
37     build(u*2, l, mid);
38     build(u*2+1, mid+1, r);
39     push_up(u);
40 }
41 
42 void add(int u, int l, int r, int x, int y, int val)
43 {
44     int tmpDel = state[u]&val;  //对当前段与删除标签进行求与，得到的即为当前段可置0的位置的集合
45     if(tmpDel==0) return;   //如果没有位置可以置为0，则直接退出
46     if(l==r)
47     {
48         minv[u] ^= tmpDel;
49         state[u] ^= tmpDel;
50         return;
51     }
52 
53     int mid = (l+r)>>1;
54     if(x<=mid) add(u*2, l, mid, x, y, val);
55     if(y>=mid+1) add(u*2+1, mid+1, r, x, y, val);
56     push_up(u);
57 }
58 
59 int query(int u, int l, int r, int x, int y)
60 {
61     if(x<=l && r<=y)
62         return minv[u];
63 
64     int ret = INF;
65     int mid = (l+r)>>1;
66     if(x<=mid) ret = min(ret, query(u*2, l, mid, x, y));
67     if(y>=mid+1) ret = min(ret, query(u*2+1, mid+1, r, x, y));
68     push_up(u);
69     return ret;
70 }
71 
72 int main()
73 {
74     int n, m;
75     scanf("%d%d", &n,&m);
76     build(1,1,n);
77     int op, L, R, val;
78     while(m--)
79     {
80         scanf("%d", &op);
81         if(op==0)
82         {
83             scanf("%d%d", &L, &R);
84             printf("%d
", query(1,1,n,L,R));
85         }
86         else
87         {
88             scanf("%d%d%d", &L,&R,&val);
89             add(1,1,n,L,R,(val^Int_Max));   //对val进行按位取反。
90         }
91     }
92 }

View Code