在该题的时候第120行发现TREE.query返回值是inline int 而 total 是结构体cnt型,但是不知道要怎么改了
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
// by_HJF_mkcpp+ and xwzy Thanks_for_GWT&ZM&ZYM(Ren)
// Working_BGM Thanks_for X_Tale-Boss_Rush by NyxTheShield
#pragma GCC optimize(3)//o3 optimize
using namespace std;
inline void set_file_IO(string);
inline void close_IO(void);
inline int read(void);
inline void put(long long x);
inline void work(void);
class binary_index_tree {
private:
static const int binaryIndexTreeSize = 1100000;
int sum[binaryIndexTreeSize];
virtual inline int lowbit(int index) {
return index & -index;
}
virtual inline int getSum(int index) {//get sum funktion is our direction
int result = 0;
for (; index; index -= lowbit(index)) {
result += sum[index];
}
return result;
}
public:
virtual inline query(int leftBound, int rightBound) {
return getSum(rightBound) - getSum(leftBound-1);
}
virtual inline int query(int index) {
int result = sum[index], lca = index - lowbit(index);
for (--index; index != lca; index -= lowbit(index)) {
result -= sum[index];
}
return result;
}
virtual inline void edit(int index, int delta, int n) {
for (;index <= n; index += lowbit(index)) {
sum[index] += delta;
}
}
};
int main(void) {
#ifndef ONLINE_JUDGE
set_file_IO("sequence");
#endif
ios::sync_with_stdio(false);
work();
#ifndef ONLINE_JUDGE
close_IO();
#endif
return 0;
}
struct cnt{
int flag;
long long laz1, laz2;
inline int cnt friend operator - (const cnt &s, const cnt &a)
{
return (cnt){s.flag-a.flag, s.laz1-a.laz2, s.laz2-a.laz2};
}
};
typedef long long llint;
const int MAX_Size=400000;
struct meeting{
int x;
int y;
int z;
int n;//use it to rememeber the position
}a[MAX_Size];
struct meeting2{
int w;
int pos;//world position
int n;//value position
}s[MAX_Size];
inline bool cmp2(meeting o1,meeting o2){
return o1.z < o2.z;
}
inline bool cmp1(meeting2 o1,meeting2 o2){
return o1.w < o2.w;
}
long long n, q;
inline void work(void) {
//by xwzy
//LET US START TO WORKING HERE!!
//we must read the value first.
n = read();
q = read();
for(int i=0; i<n; i++){
s[i].w = read();
s[i].pos = read();
s[i].n = i;
}
for(int i=0; i<q; i++){
a[i].x = read();
a[i].y = read();
a[i].z = read();
a[i].n = i;
}
//---------------------------------------------
//find the value which smaller than a[i].w in pos
sort(a ,a + n, cmp1);
sort(s ,s + n, cmp2);//from small to high
bool cntpos[MAX_Size];
long long ans[MAX_Size];
binary_index_tree TREE;//use the class binary_index_tree
int j=0;
for(int i=0; i<n; i++)
{
while(j+1<n and s[j].w<=a[i].z)
TREE.edit(s[j].n, s[++j].pos, n);
cnt totle = TREE.query(a[i].y, a[i].x);
if (!totle.flag) {cntpos[a[i].n] = 1; continue;}
ans[a[i].n] = (totle.laz2*totle.flag - 2*totle.laz1*totle.laz1 + totle.laz1*totle.laz1);
//complete square formula
}
for(int i=0; i<q;i++)
if(cntpos[i]) puts("empty");
else put ( ans[i]) ;
return;
}
inline void set_file_IO(string name) {
//freopen((name + ".in" ).c_str(), "r", stdin);
//freopen((name + ".out").c_str(), "w", stdout);
}
inline void close_IO(void) {
fclose(stdin);
fclose(stdout);
}
#include<cctype>
//fast read & write
inline int read(void) {
char ch;
while (!(isdigit(ch = getchar()) || ch == '-'));
int res = 0, flg = 1;
if (ch == '-') flg = -1;
else res = ch - '0';
while (isdigit(ch = getchar()))
(res *= 10) += ch - '0';
return res * flg;
}
inline void put(long long x){
if (!x) {puts("0"); return;}
if (x < 0) x = -x, putchar('-');
int b[20], lenb = 0;
while (x){
b[++lenb] = x % 10;
x /= 10;
}
for(int i = lenb; i >= 1; i --)
putchar((char)(b[i] + '0'));
puts("");
}