说明：这是去年写了一半的东西，一直存在草稿箱里，今天整理东西的时候才发现，还是把它发表出来吧。。
以下所有题目来自Lrj的《训练指南》
LA 2191
单点修改，区间和 Fenwick直接搞
UVa 12299
给出n个数，支持循环移动某些数（<30个）,然后问区间最小值
因为移动小于30个数，所以直接单点修改就行，线段树。
LA 4108
类似线段树，每次插入一个建筑时想线段树一样二分区间，当遇到一个完整的区间时，修改或返回，否则继续二分区间。Nlogn.
UVa 11525
有题解说可以逆向考虑用线段树，我没明白怎么回事。
说一下我的做法：
考虑问题(k,n)表示1~k的全排列中第n个。显然1~k的全排列可以分为k种，每种有(k-1)!种情况，那么如果确定了第n个排列属于哪一种，问题就转化为了(k-1,m);
再考虑题目的输入。N的输入形式正好是按以上思想给出的，那么我们是需要把这个式子转化为标准形式即可。
判断每个Si，若Si>(k-i+1)，就要”进位”。所以从后向前扫描，可以在O(n)时间内解决。
LA 4730
并查集+线段树。用并查集维护每个州，同时维护每个州的上端点(up)和下端点(down)。
用线段树维护[a,b]内有多少个城市。方法是连接A和B时,[A.down,A.up]-=A.count; [B.down,B.up]-=B.count; [new.down,new.up]+=new.count;
二维线段树
先存一下(以下代码仅供参考 准确性无法保证233)
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#define RS(x) (x*2+1)
#define LS(x) (x*2)
#define bigger(a,b) ((a)>(b)?(a):(b))
#define minner(a,b) ((a)<(b)?(a):(b))
#define MAXN (2000+10)
#define root (1)
#define INF (9999999)
using namespace std;
struct Segment_Tree_2D{
struct treeY{
int max,min;
int L,R;
int mid;
};
typedef struct treeY treeY;
struct treeX{
treeY T[MAXN];
int L,R;
int mid;
};
typedef struct treeX treeX;
int x1,x2,y1,y2,val,max_ans,min_ans,x0,y0;
treeX t[MAXN];
void queryY(int f,int r,int fa,int p){//ok
if (r>t[fa].T[p].R) r=t[fa].T[p].R;
if (f<t[fa].T[p].L) f=t[fa].T[p].L;
if (f==t[fa].T[p].L&&r==t[fa].T[p].R){
max_ans=bigger(max_ans,t[fa].T[p].max);
min_ans=minner(min_ans,t[fa].T[p].min);
}else{
int mid=t[fa].T[p].mid;
if (r>mid) queryY(mid+,r,fa,RS(p));
if (f<=mid) queryY(f,mid,fa,LS(p));
}
}
void queryX(int f,int r,int p){//ok
if (r>t[p].R) r=t[p].R;
if (f<t[p].L) f=t[p].L;
if (f==t[p].L&&r==t[p].R){
queryY(y1,y2,p,root);
}else{
int mid=t[p].mid;
if (r>mid) queryX(mid+,r,RS(p));
if (f<=mid) queryX(f,mid,LS(p));
}
}
void modifyY(int fa,int p){//ok
if (y0==t[fa].T[p].L&&y0==t[fa].T[p].R){
t[fa].T[p].min=val;
t[fa].T[p].max=val;
}else{
int mid=t[fa].T[p].mid;
if (y0>mid) modifyY(fa,RS(p));
if (y0<=mid) modifyY(fa,LS(p));
}
t[fa].T[p].max=bigger(t[fa].T[LS(p)].max,t[fa].T[RS(p)].max);
t[fa].T[p].min=minner(t[fa].T[LS(p)].min,t[fa].T[RS(p)].min);
}
void maintainY(int fa,int p){//ok
if (y0==t[fa].T[p].L&&y0==t[fa].T[p].R){
t[fa].T[p].min=minner(t[LS(fa)].T[p].min,t[RS(fa)].T[p].min);
t[fa].T[p].max=bigger(t[LS(fa)].T[p].max,t[RS(fa)].T[p].max);
}else{
int mid=t[fa].T[p].mid;
if (y0>mid) maintainY(fa,RS(p));
if (y0<=mid) maintainY(fa,LS(p));
}
t[fa].T[p].max=bigger(t[fa].T[LS(p)].max,t[fa].T[RS(p)].max);
t[fa].T[p].min=minner(t[fa].T[LS(p)].min,t[fa].T[RS(p)].min);
}
void modifyX(int p){
if (x0==t[p].L&&x0==t[p].R){
modifyY(p,root);
}else{
int mid=t[p].mid;
if (x0>mid) modifyX(RS(p));
if (x0<=mid) modifyX(LS(p));
maintainY(p,root);
}
} void query(){max_ans=-INF;min_ans=INF;queryX(x1,x2,root);}
void modify(){modifyX(root);}
};
typedef struct Segment_Tree_2D ST2;
ST2 t;
int main()
{
int i,j,n,m,temp,q;
char cmd[];
scanf("%d%d",&n,&m);
for (i=;i<=n;i++){
for (j=;j<=m;j++){
scanf("%d",&temp);
t.x0=i; t.y0=j;
t.modify();
}
}
scanf("%d",&q);
for (i=;i<q;i++){
scanf("%s",cmd);
if (cmd[]=='q'){
scanf("%d%d%d%d",&t.x1,&t.y1,&t.x2,&t.y2);
t.query();
printf("%d %d\n",t.max_ans,t.min_ans);
}else{
scanf("%d%d",&t.x0,&t.y0);
t.modify();
}
}
return ;
}