求助巨佬,原题是团队私题,就不公开了,谁能帮我看看他有什么问题呢
  • 板块学术版
  • 楼主uFTvL9
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/8/14 21:28
  • 上次更新2023/11/4 10:39:17
查看原帖
求助巨佬,原题是团队私题,就不公开了,谁能帮我看看他有什么问题呢
411963
uFTvL9楼主2021/8/14 21:28

在该题的时候第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("");
}
2021/8/14 21:28
加载中...