【题意】：给出n个2*2的矩阵和m个区间查询[i,j]，对于每个查询输出矩阵Pi,j=Ai × Ai+1 × ... × Aj 。

【题解】：普通的矩阵乘法，观察到1<=n,m<=30,000，如果用朴素的方法时间复杂度高达O(nm)，显然是不可以接受的。
              这里可以用线段树的查询思想，把中间有用的值保存下来，以后就可以用O(1)的得到。

【代码】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 using namespace std;
 5 #define maxn 32768
 6 int r, n, m;
 7 struct Mat {
 8     int val[2][2];
 9     void zero() {
10         memset(val, 0, sizeof(val));
11     }
12 }x[(maxn<<1)+1];
13 
14 int LC(int i) {return i << 1;}
15 int RC(int i) {return LC(i)^1;}
16 
17 Mat operator *(const Mat &a, const Mat &b) {
18     Mat tmp;
19     tmp.zero();
20     for(int k = 0; k < 2; k++) {
21         for(int i = 0; i < 2; i++) {
22             if(a.val[i][k]) {
23                 for(int j = 0; j < 2; j++) {
24                     tmp.val[i][j] += a.val[i][k] * b.val[k][j];
25                     if(tmp.val[i][j] >= r) tmp.val[i][j] %= r;
26                 }
27             }
28         }
29     }
30     return tmp;
31 }
32 
33 Mat query(int p, int left, int right, int l, int r) {//线段树的查询思想
34     if(left == l && right == r) return x[p];
35     int mid = (left + right) >> 1;
36     if(r <= mid) return query(LC(p), left, mid, l, r);
37     else if(l > mid) return query(RC(p), mid + 1, right, l, r);
38     else return query(LC(p), left, mid, l, mid) * query(RC(p), mid + 1, right, mid + 1, r);
39 }
40 
41 int main() {
42     bool flag = false;
43     while(~scanf("%d%d%d", &r, &n, &m)) {
44         int st = 1;
45         while(st < n) st <<= 1;
46         for(int i = 0; i < n; i++) 
47             for(int j = 0; j < 2; j++)
48                 for(int k = 0; k < 2; k++)
49                     scanf("%d", &x[st+i].val[j][k]);
50         for(int i = st - 1; i; i--) x[i] = x[LC(i)] * x[RC(i)];
51         while(m--) {
52             if(flag) printf("\n");
53             else flag = true;
54             int le, ri;
55             scanf("%d%d", &le, &ri);
56             Mat ans = query(1, 1, st, le, ri);
57             printf("%d %d\n%d %d\n", ans.val[0][0], ans.val[0][1], ans.val[1][0], ans.val[1][1]);
58         }
59     }
60     return 0;
61 }