感觉这套题目挺不错的
A：
做过很多变了
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 #define INF 1e9 7 #define inf (-((LL)1<<40)) 8 #define lson k<<1, L, mid 9 #define rson k<<1|1, mid+1, R10 #define mem0(a) memset(a,0,sizeof(a))11 #define mem1(a) memset(a,-1,sizeof(a))12 #define mem(a, b) memset(a, b, sizeof(a))13 #define FOPENIN(IN) freopen(IN, "r", stdin)14 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)15 template T CMP_MIN(T a, T b) { return a < b; }16 template T CMP_MAX(T a, T b) { return a > b; }17 template T MAX(T a, T b) { return a > b ? a : b; }18 template T MIN(T a, T b) { return a < b ? a : b; }19 template T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }20 template T LCM(T a, T b) { return a / GCD(a,b) * b; }21 22 typedef __int64 LL;23 //typedef long long LL;24 const int MAXN = 50005;25 const int MAXM = 100005;26 const double eps = 1e-10;27 const LL MOD = 1000000007;28 29 int T, N;30 int num[MAXN<<2];31 int l, r, id, val;32 33 void update(int k, int L, int R)34 {35 if(L == R){ num[k] += val; return ;}36 37 int mid = (L + R) >> 1;38 39 if(id <= mid) update(lson);40 41 else update(rson);42 43 num[k] = num[k<<1] + num[k<<1|1];44 }45 46 int query(int k, int L, int R)47 {48 if(R < l || r < L) return 0;49 50 if(l<=L && R<=r) return num[k];51 52 int mid = (L + R) >> 1;53 54 return query(lson) + query(rson);55 56 }57 58 int main()59 {60 scanf("%d", &T);61 for(int t = 1; t <= T; t ++ )62 {63 mem0(num);64 scanf("%d", &N);65 for(id=1;id<=N;id++)66 {67 scanf("%d%*c", &val);68 update(1, 1, N);69 }70 char str[10];71 printf("Case %d:\n", t);72 while(scanf("%s", str) && strcmp(str,"End")!=0)73 {74 if(!strcmp(str, "Add")) {75 scanf("%d %d%*c", &id, &val);76 update(1, 1, N);77 }78 else if(!strcmp(str, "Sub")) {79 scanf("%d %d%*c", &id, &val);80 val=-val; update(1, 1, N);81 }82 if(!strcmp(str, "Query")) {83 scanf("%d %d%*c", &l, &r);84 printf("%d\n", query(1, 1, N));85 }86 }87 }88 return 0;89 }
B:
同上：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 #define INF 1e9 7 #define inf (-((LL)1<<40)) 8 #define lson k<<1, L, mid 9 #define rson k<<1|1, mid+1, R10 #define mem0(a) memset(a,0,sizeof(a))11 #define mem1(a) memset(a,-1,sizeof(a))12 #define mem(a, b) memset(a, b, sizeof(a))13 #define FOPENIN(IN) freopen(IN, "r", stdin)14 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)15 template T CMP_MIN(T a, T b) { return a < b; }16 template T CMP_MAX(T a, T b) { return a > b; }17 template T MAX(T a, T b) { return a > b ? a : b; }18 template T MIN(T a, T b) { return a < b ? a : b; }19 template T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }20 template T LCM(T a, T b) { return a / GCD(a,b) * b; }21 22 typedef __int64 LL;23 //typedef long long LL;24 const int MAXN = 2000005;25 const int MAXM = 100005;26 const double eps = 1e-10;27 const LL MOD = 1000000007;28 29 int M, N;30 int num[MAXN<<2];31 int l, r, id, val;32 33 void update(int k, int L, int R)34 {35 if(L == R){ num[k] = val; return ;}36 37 int mid = (L + R) >> 1;38 39 if(id <= mid) update(lson);40 41 else update(rson);42 43 num[k] = MAX( num[k<<1], num[k<<1|1]);44 }45 46 int query(int k, int L, int R)47 {48 if(R < l || r < L) return -INF;49 50 if(l<=L && R<=r) return num[k];51 52 int mid = (L + R) >> 1;53 54 return MAX( query(lson), query(rson) );55 56 }57 58 int main()59 {60 while(scanf("%d %d", &N, &M) == 2)61 {62 mem0(num);63 for(id=1;id<=N;id++)64 {65 scanf("%d%*c", &val);66 update(1, 1, N);67 }68 char ch;69 for(int i=0;i
C:
拿到最初的状态的结果，后面反转的序列都可以递推得到
1 #include
D:
感觉这个提又启发了另一种思路，题义是说每次在下表为a的位置插入一个数B，求最终的整个序列的结果。
树里的每个值表示的是这个区间有多少个空余的位置，这样的话将B插入到A位置就是指B以前需要有A个空余的位置。
只是这里的更新操作里的递归条件不是与mid值比较，而是比较当前插入的这个数所需的空闲位置的数量如左右字节点的数量比较
1 void update(int k, int L, int R, int x) 2 { 3 if(L == R) { pre[k] = r; ans[L] = val; return ; } 4 5 int mid = (L+R)>>1; 6 7 if(x <= pre[k<<1]) update(lson, x); 8 9 else update(rson, x-pre[k<<1]);10 11 pre[k] = pre[k<<1] + pre[k<<1|1];12 } 1 #include
E:
据说是涉及到一个叫反素数的概念
1 #include
F:
裸的线段树的区间延时标记
1 #include
G:
区间延时标记与查询
1 #include
W:
矩形K次的并，可以作为自己的模板了
1 #include