/* Time complexity: O(M * sqrt(N) * log(N)) Use the property A%B = A - (A/B)*B Processing 3td type query can be divided in 2 parts: processing big groups with equal Y/i( Lj<=i<=Rj ), O(sqrt(N)) the biggest groups. One need to use segment tree or fenwick tree to track and get number of families on intervals. The smaller groups are processed by bruteforce. */ #include #include #include #include #include #include #include #include #include #include #include #define X first #define Y second using namespace std; const int maxn = 100100; long long r[maxn], a[maxn]; int n, m; void modify(int x, long long y) { for (; x < maxn; x = (x|(x+1))) r[x] += y; } long long sum(int x) { long long res = 0; for (; x >= 0; x = ((x&(x+1)) - 1)) res += r[x]; return res; } long long calc(long long x) { long long res=0; int minst = x+1; for (int i=1; i <= 110; i++) { int st, fin=minst-1; st=(x/(i+1))+1; if (fin==0) return res; res+=(sum(fin) - sum(max(st-1, 0)) )*(long long)i; minst=st; } for (int i=1; i>m; for (int i=1; i<=m; i++) { long long aa, bb; cin>>aa>>bb; gr += bb; a[aa] += bb*aa; modify(aa, bb*aa); } cin>>n; for (int i=1; i<=n; i++) { char ss[3]; cin>>ss; if ( ss[0] == '+' ) { int x; cin>>x; modify(x, x); a[x]+=x; gr++; } if ( ss[0] == '-' ) { int x; cin>>x; modify(x, -x); a[x]-=x; gr--; } if ( ss[0] == '?' ) { long long x; cin>>x; long long S = gr*x, T; T = calc(x); cout<< S-T <