分块思想

CF348http://codeforces.com/contest/348/problem/C

题意：一个n个元素的序列，m个下标集合，q个操作，两种操作1：给你一个集合，求序列中下标在集合中的元素的sum；2：给你一个集合，把序列中下标在集合中的元素都加X; 1<= n,m,q <= 10^5; 并且题目中明确说明所有集合的元素个数小于10^5；

分析：http://codeforces.com/blog/entry/9031?locale=en

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<cmath>
  5 #include<iostream>
  6 #include<algorithm>
  7 #include<vector>
  8 #include<queue>
  9 using namespace std;
 10 typedef long long LL;
 11 const int N = 100000+10;
 12 const int SZ = 315;
 13 vector<int> g[N];
 14 int id[N],id_sz;
 15 int n,m,q;
 16 LL a[N];
 17 int ins[N][N/SZ+10];
 18 bool inset[N/SZ+10][N];
 19 LL sum[N/SZ+10],tar[N/SZ+10];
 20 void solve(){
 21     LL an;
 22     while (q--) {
 23         char s[5];
 24         int v,x;
 25         scanf("%s",s);
 26         if (s[0] == '?') {
 27             scanf("%d",&v);
 28             v--;
 29             if (id[v] == -1) {
 30                 an = 0;
 31                 for (int i = 0; i < g[v].size(); i++) {
 32                     an += a[g[v][i]];
 33                 }
 34                 for (int i = 0; i < id_sz; i++) {
 35                     an += (LL)tar[i] * ins[v][i];
 36                 }
 37                 cout<<an<<endl;
 38             }else {
 39                 an = sum[id[v]];
 40                 for (int i = 0; i < id_sz; i++) {
 41                     an += (LL)tar[i] * ins[v][i];
 42                 }
 43                 cout<<an<<endl;
 44             }
 45         }else {
 46             scanf("%d%d",&v,&x);
 47             v--;
 48             if (id[v] == -1) {
 49                 for (int i = 0; i < g[v].size(); i++) {
 50                     a[g[v][i]] += x;
 51                 }
 52                 for (int i = 0; i < id_sz; i++) {
 53                     sum[i] += ins[v][i] * x;
 54                 }
 55             }else {
 56                 tar[id[v]] += x;
 57             }
 58         }
 59 
 60     }
 61 }
 62 int main(){
 63     while (~scanf("%d%d%d",&n,&m,&q)) {
 64         for (int i = 0; i < n; i++) scanf("%lld",a+i);
 65         memset(id,-1,sizeof(id));
 66         id_sz = 0;
 67         for (int i = 0; i < m; i++) g[i].clear();
 68         for (int i = 0; i < m; i++) {
 69             int cnt; scanf("%d",&cnt);
 70             LL tmp = 0;
 71             while (cnt--) {
 72                 int x; scanf("%d",&x); x--;
 73                 g[i].push_back(x);
 74                 tmp += a[x];
 75             }
 76             if (g[i].size() > SZ) {
 77                 for (int j = 0; j < g[i].size(); j++)
 78                     inset[id_sz][g[i][j]] = 1;
 79                 sum[id_sz] = tmp;
 80                 id[i] = id_sz++;
 81             }
 82         }
 83         for (int i = 0; i < n; i++) {
 84             for (int j = 0; j < g[i].size(); j++) {
 85                 for (int k = 0; k < id_sz; k++) {
 86                     ins[i][k] += inset[k][g[i][j]];
 87                 }
 88             }
 89         }
 90         solve();
 91     }
 92     return 0;
 93 }
 94 /*
 95 5 3 5
 96 5 -5 5 1 -4
 97 2 1 2
 98 4 2 1 4 5
 99 2 2 5
100 ? 2
101 + 2 4
102 ? 1
103 + 2 1
104 ? 1
105 */

View Code