http://www.lydsy.com/JudgeOnline/problem.php?id=2002
题意+思路： 同codeforces 13 E holes.
1/* *********************************************** 2Author :111qqz 3Created Time :2016年02月21日 星期日 02时29分39秒 4File Name :code/bzoj/2002.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=2E5+7; 34int n,m; 35int siz = 450; //sqrt(2E5) 36int a[N]; 37int pos[N]; 38int cnt[N]; 39int nxt[N]; 40int end[N]; 41 42 43void go( int x) 44{ 45 int ans = 0 ; 46 while (1) 47 { 48 if (x>=n) 49 { 50 printf("%d\n",ans); 51 break; 52 } 53 ans +=cnt[x]; 54 x = nxt[x]; 55// cout<<"nxt[x]:"<<nxt[x]<<endl; 56 } 57} 58void update ( int i,int j) 59{ 60 if (j>=n) 61 { 62 cnt[i]=1; 63 nxt[i]=n; 64 end[i]=i; 65 } 66 else 67 { 68 if (pos[i]==pos[j]) 69 { 70 cnt[i] = cnt[j] + 1; 71 nxt[i] = nxt[j]; 72 end[i]=end[j]; 73 } 74 else 75 { 76 cnt[i] = 1; 77 nxt[i] = j; 78 end[i] = end[j]; 79 } 80 } 81} 82int main() 83{ 84 #ifndef ONLINE_JUDGE 85 freopen("code/in.txt","r",stdin); 86 #endif 87 88 scanf("%d",&n); 89 for ( int i = 0 ; i < n ;i++) 90 { 91 scanf("%d",&a[i]); 92 pos[i] = i/siz; 93 } 94 95 for ( int i = n - 1 ; i >= 0 ; i--) update(i,i+a[i]); 96 97 scanf("%d",&m); 98 while (m--) 99 { 100 int opt; 101 scanf("%d",&opt); 102 if (opt==1) 103 { 104 int x; 105 scanf("%d",&x); 106 go(x); 107 } 108 else 109 { 110 int x,y; 111 scanf("%d %d",&x,&y); 112 a[x]=y; 113 update(x,x+a[x]); 114 int p = pos[x]*siz; 115 for ( int i = x-1 ; i >= p ; i--) update(i,i+a[i]); 116 } 117 } 118 119 #ifndef ONLINE_JUDGE 120 fclose(stdin); 121 #endif 122 return 0; 123}
http://codeforces.com/problemset/problem/13/E 题意：给你n个洞，进入某个洞后会跑到另一个洞，到了另一个洞之后又可能会继续到下一个洞，问你从一个洞进去，钻了几个洞才会出来，在哪个洞出来
http://codeforces.com/contest/613/problem/B 题意：有n个技能，初始每个技能的level为a[i]，每个技能最大level为A(不妨称为满级技能)，设满级技能个数为maxnum,最小的技能level为minval,问如何将m个技能点分配到n个技能上使得cfmaxsum+cmminval (n<=1E5,a[i],A<=1E9,cf,cm<=1E3,m<=1E15)
http://www.lydsy.com/JudgeOnline/problem.php?id=3289
题意：中文题目，简单来说就是求某一区间内的逆序对数。
思路：逆序对数想到树状数组。不过写莫队转移的时候没弄明白。。。。大概是树状数组理解的还不够透彻。。。需要复习一下了。。。
There are two types of problems solvable by partial sum.
1.Problems which you are asked to answer some queries about the sum of a part of elements (without modify queries).
http://acm.hdu.edu.cn/showproblem.php?pid=5416 # 题意：给出一棵树（n<=1E5），定义二元函数函数f(u,v) (u可以等于v)表示节点u到节点v经过的路径的权值的异或和。给出q组查询（q<=10），每组一个s,问有多少对无序点对（u,v）满足f(u,v)=s. 思路：类似codeforces #340 div 2 E XOR and Favorite Number 先dfs,处理出从根节点都任意节点的异或前缀和。然后对于每个询问o(n)扫一遍，统计sum[i]^s出现多少次。 总的时间复杂度为O(Tqn);
http://acm.hdu.edu.cn/showproblem.php?pid=5327 题意：问给出的区间[a,b]中有多少个美丽数，美丽数的定义是所有数字都不相同，如123是，100不是，333也不是。 思路：预处理1..100000的美丽数，可以把每个数字拆开放在set里，比较set的size和位数来实现。 然后用前缀和。
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3693 题意： n+2个人取吃饭，每人w元，每k个人可以少付一个人的钱，问最后两个教练每人要付多少钱。
http://codeforces.com/contest/373/problem/C 题意：n个袋鼠，每个袋鼠的size为a[i],一只袋鼠的size至少是另一只两倍时才能将它装下，被装下的袋鼠不能再装别的袋鼠且不能被看见。问能看见的袋鼠最少是多少。 思路：贪心。最多有n/2个袋鼠被装下。先排序，然后贪心即可。
http://acm.hdu.edu.cn/showproblem.php?pid=4638 题意：给定一个序列，序列由1-N个元素全排列而成，求任意区间连续的段数。例如序列2,3,5,6,9就是三段(2, 3) (5, 6)(9)。 思路：增加一个元素，如果它两边的元素都出现了，那么段数-1（相当于把两段连接起来合并成了一段），如果两边元素都没有出现，那么段数+1.反过来，减少一个元素时，如果两边元素都出现了，俺么段数+1（相当于把完整的一段断开成两段），如果两边元素都没有出现，那么段数-1.操作可以O(1)完成。。。上莫队。 因为id大小最大才100000，所以判断某个元素是否出现开一个100000大小的布尔数组即可（我竟然傻逼得去用set….然后华丽丽得TLE了2333）
http://codeforces.com/contest/614/problem/C # 题意：给一个多边形和多边形外一定点，多边形绕定点旋转，问多边形扫过的面积。 思路：简单计算几何，找到多边形距离定点的最大和最小距离R和r,答案就是(R^2-R^2)*PI 需要注意的是：最大距离一定是从某点上取得，但是最小距离可能不在顶点上，而在某条边上。
写了几道莫队，总结下。 目前只会区间莫队。。树上莫队以后再补。
莫队算法学习
https://ac.2333.moe/Problem/view.xhtml?id=1457 题意：求一段区间内数字个数的立方和。 思路：由于一共才1E5,而数字1E9,所以先离散化，再莫队，类似小z的袜子。 注意 ：%lld会WA,要用%I64d
http://acm.hdu.edu.cn/showproblem.php?pid=5145 题意：有n个女孩，编号1..n,第i个女孩在第a[i]个教室,m次访问，每次访问编号[L,R]的女孩，处于同一个教室的女孩一次只能访问一个，问有多少种访问方案。两个不同的方案当且仅当访问的顺序有所不同。
http://codeforces.com/contest/617/problem/E
题意：给出n个数，m个查询，每个查询给定l,r，问在区间【l,r】内，有多少对i,j,满足i^(i+1)^(i+2)^…^j的值为给定的常数k.
http://acm.hdu.edu.cn/showproblem.php?pid=5213 题意：n个数，m个查询，每个查询由4个数l1,r1,l2,r2构成，询问分别从[l1,r1]和[l2,r2]中各取一个数，和为给定的常数k的方案数。
http://codeforces.com/contest/220/problem/B
题意：n个数，m个查询区间，对于每一个区间[l,r]输出区间中cnt[x]==x的数的个数。 # 思路：首先，a[i]很大。。。但是n最大才1e5…每个a[i]最多出现1E5次。。所以对于大于1E5的a[i]对答案没有贡献。其次，上莫队算法。
http://codeforces.com/problemset/problem/86/D # 题意：Ks为区间内s的数目，求区间[L,R]之间所有KsKss的和 # 思路：莫队算法，和小z的袜子差不多。不明白第一次tle#54是什么情况。把每一块的大小改成了常数之后就过了。 # 再交一遍就过了。。不过貌似根据最大数据把siz大小设置成一个常数比根号n要块很多==
2038: [2009国家集训队]小Z的袜子(hose)
Time Limit: 20 Sec Memory Limit: 259 MB Submit: 5327 Solved: 2461 [Submit][Status][Discuss] Description
http://codeforces.com/contest/625/problem/D 题意：问能否找到一个s,满足s+s的反转=k 思路：如果是回文数。。。那么显然满足。除以2就可以得到答案。