现在正在上课，但我还是要同步更新博文。。。\滑稽
先讲一个离散化，就是把几个离的特别远的数在不影响结果的情况下，变成相近的数。倒是没什么影响，但应用在数组下标的话可以节约空间。（貌似和hash有点像）
直接拍代码
给定n个数，如果一个数出现x次，则对答案的贡献为x^2。 求这n个数对答案的贡献是多少。 n<=100000。 f[i] i这个数字出现了几次 cin>>n; for (int i=1; i<=n; i++) cin>>A[i]; ... 离散化 for (int i=1; i<=n; i++) {t[i].x=A[i]; t[i].y=i;} sort(t+1,t+n+1,cmp); for (int i=1; i<=n; i++) while (!A[t[i].y]==t[i].x); A[t[i].y] 一定等于 t[i].x for (int i=1; i<=n; i++) { if (i==1 || t[i].x!=t[i-1].x) now++; A[t[i].y]=now; } ... for (int i=1; i<=n; i++) f[A[i]]++; for (int i=1; i<=n; i++) ans+=f[i]*f[i]; cout<<ans;前缀和是个好东西，可以方便的操作。（每次加前一个，找区间时整体相减）
来一个矩阵前缀和
给定一个n*n的矩阵ai,j以及m个询问。 每次询问一个子矩阵的和。 要求一个O(n*n+m)的做法。 for (i=1; i<=n; i++) for (j=1; j<=n; j++) f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j]; f[i][j] 左上角在(1,1)，右下角在(i,j)的和是多少 for (i=1; i<=m; i++) { cin>>x>>y>>X>>Y; cout<<f[X][Y]-f[x-1][Y]-f[X][y-1]+f[x-1][y-1]<<endl; }还有一个差值的数组，f[]中存的是每个数和前一个数的差值，特殊的，f[1] = 本身。
附赠代码：
cin>>n; for (i=1; i<=n; i++) cin>>a[i]; cin>>m; for (i=1; i<=m; i++) { cin>>A>>B>>C; f[A]+=C; f[B+1]-=C; } for (i=1; i<=n; i++) f[i]=f[i-1]+f[i]; for (i=1; i<=n; i++) cout<<a[i]+f[i]<<' ';Captain最巨!!!
转载于:https://www.cnblogs.com/DukeLv/p/8421020.html
